动态规划问题之计算最大连续和

动态规划问题之计算最大连续和

**58539-**连续最大和

https://www.nowcoder.com/practice/5a304c109a544aef9b583dce23f5f5db?tpId=85&&tqId=29858&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

假设sum[j-1]是以数组中第nums[j-1]为最后一个元素的一段子数的最大和

sum[j]是以数组中第nums[j]为最后一个元素的一段子数组的最大和

那么sum[j] = max(sum[j-1],0)+nums[j],下面代码中用sum1表示sum[j-1],sum2表示sum[j],如果计算出更大的子数组和则保存到result中，如果sum[j]，及sum2都小于0，则置为0，因为他加上数组下一个数字，不会计算出更大的子数组和。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int size;
    cin>>size;
    vector<int> nums(size);
    for(int i=0;i<nums.size();++i)
        cin>>nums[i];
    int sum1 = 0,sum2 = 0;
    int result = nums[0];
    for(int j=0;j<nums.size();++j)
    {
        sum2 = sum1>0?nums[j]+sum1:nums[j];
        if(sum2>result)
            result = sum2;
        if(sum2<0)
            sum2 = 0;
        sum1 = sum2;
    }
    cout<<result<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/HuiDiExAg/article/details/110204361