连续最大和

题目来源

牛客网：连续最大和

题目描述

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

输入描述

输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。.

输出描述

所有连续子数组中和最大的值。

示例1

输入

3
-1 2 1

输出

3

思路分析

• 数组v保存数据，定义一个sum保存临时的最大值，max保存比较过后的最大值
• 遍历数组，数组元素和用sum表示，如果之前的sum值小于0，则可以被舍弃，用当前v[i]替代其值，因为要求的是最大连续和，如果sum值大于0，则保留之前的sum，并且需要加上当前的v[i]
• 每次sum的值变化，都要与max进行比较，两者之间较大的就是遍历到当前位置的连续最大和
• 状态方程式： max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )，这个方程表示的含义是，以下标为 i 结尾的数组的最大序列和，即每一个位置为结尾，之前的最大序列和都是该位置前一个位置的最大序列和加上当前位置的元素的值，与当前位置元素的值比较，两者之前较大的。而当然，如果前一个位置的最大序列和小于0，则最大序列和是当前位置元素的值。

代码展示

#include<iostream>
#include<vector>

using namespace std;
int main()
{
    
    vector<int> v;
    int n = 0;
    while (cin >> n)
    {
    
        //vector添加元素，先设置容器大小
        v.resize(n);
        for (int i = 0; i < n; i++)
        {
    
            cin >> v[i];
        }
        int sum = v[0];
        int max = v[0];
        for (int i = 0; i < v.size(); i++)
        {
    
            if (sum < 0)
            {
    
                //sum的值若小于0，则v[i]之前的元素被舍弃
                sum = v[i];
            }
            else
            {
    
                //如果sum值大于0，为了得到之前大于0的部分，无论正负
                //都要加上当前v[i]的值
                sum += v[i];
            }
            if (sum > max)
            {
    
                max = sum;
            }
        }
        cout << max;
    }
    return 0;
}

总结

• vector类对象添加元素，先使用v.resize()设置容器大小