首页 > 编程语言 >Problem P14. [算法课动态规划]连续数组最大和

Problem P14. [算法课动态规划]连续数组最大和

时间:2022-09-21 13:34:01浏览次数:76  
标签:nums curnum cursum int 算法 P14 数组 Problem maxsum

感觉很简单的一道题,curnum存下连续数组和大于0的数值,maxnum存下最大连续数组和,curnum从数组头开始,遍历数组,+= 数组值,当curnum大于0时,那么即便紧接着的后面有一个很大的数组和,但是加上curnum会更大,但是curnum小于0的时候,会损害后面的数组和,所以curnum现在所代表的前面的数组和就要舍弃,重置curnum=0,即从该位置重新算一个新的数组和。具体实现看代码。

#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>
#include<string>

using namespace std;

int main()
{
    vector<int> nums;
    int n = 0;
    scanf("%d", &n);
    while(n--){
        int c;
        scanf("%d", &c);
        nums.push_back(c);
    }
    int maxsum = -1;
    int cursum = 0;
    for (int i = 0; i < nums.size(); i++){
        cursum += nums[i];
        if (cursum > 0){
            if (cursum > maxsum){
                maxsum = cursum;
            }
        }else {
            cursum = 0;
        }
    }
    if (maxsum > 0){
        cout << maxsum;
    }else {
        maxsum = nums[0];
        for (int i = 0; i < nums.size(); i++){
            if (nums[i] > maxsum){
                maxsum = nums[i];
            }
        }
        cout << maxsum;
    }
    return 0;
}

标签:nums,curnum,cursum,int,算法,P14,数组,Problem,maxsum
From: https://www.cnblogs.com/understanding-friends/p/16715272.html

相关文章

  • 数据结构算法(一)之二分查找
    internalclassProgram{staticvoidMain(string[]args){varn=50;varrandom=newRandom();while......
  • 目标检测YOLO系列算法的进化史
    本文中将简单总结YOLO的发展历史,YOLO是计算机视觉领域中著名的模型之一,与其他的分类方法,例如R-CNN不同,R-CNN将检测结果分为两部分求解:物体类别(分类问题),物体位置即bounding......
  • letcode算法--15. 删除有序数组中的重复项
    给你一个升序排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。元素的相对顺序应该保持一致。由于在某些语言中不能改......
  • JS/TS算法---回溯算法
    回溯算法(backtracking)、什么是回溯法回溯法也可以叫做回溯搜索法,它是一种搜索的方式。在二叉树系列中,我们已经不止一次,提到了回溯,例如二叉树:以为使用了递归,其实还隐藏......
  • 【学习笔记】匈牙利算法
    【图论】二分图最大匹配——匈牙利算法二分图相当好理解这是百度百科的定义二分图又称作二部图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两......
  • 密码学基础之非对称加密算法
    非对称加密算法非对称加密的一般流程是服务端生成一个密钥对(私钥和公钥),然后将公钥发送给客户端。之后服务可以通过私钥加密数据发送给客户端,客户端收到消息后通过公钥解密......
  • 算法竞赛模板
    常用模板#pragmaGCCoptimize(3)#include<bits/stdc++.h>//=============全局LL================#defineintlonglong//=============全局LL==============......
  • CSP 2022 备战 高精度算法
    在考场上,有些题目,你用int只能拿30分开了longlong还是会爆这时候还得靠高精度算法来支持概念:将数字中的每一位存入数组中比如123,可以将它存入一个a[3]的数组中a[0]......
  • 【Coel.学习笔记】随机化算法:模拟退火与爬山法
    简介模拟退火(\(\text{SimulateAnneal}\))和爬山法是随机化算法,二者的原理都在于通过随机生成答案并检查,把答案逐步缩小在一个可行的区间,尽可能地靠近正确答案。在考场......
  • N皇后 【回溯算法】
    51.N皇后-力扣(LeetCode) 核心:1.按照层去选择2.使用String.copyValueOf(char[])将char数组转成StringclassSolution{List<List<String>>res;publ......