洛谷P1115 最大子段和

url: https://www.luogu.com.cn/problem/P1115

tag：
最大子数列，Kadane 算法，动态规划

思路：
使用动态规划得方法来求解，用两个变量currentSum，和maxSum，分别来维护以当前位置结尾的最大子段和以及全局的最大子段和。状态转移分别是currentSum = max(a, currentSum + a), maxSum = max(maxSum, currentSum).最后输出maxSum即可。细节：一开始可以先定义为最小值-0x3f3f3f3f这样可以避免漏掉负数，以及因为要求和所以最好开long long避免爆int。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int main()
{
    scanf("%d", &n);
    long long currentSum = -0x3f3f3f3f, maxSum = -0x3f3f3f3f;
    for (int i = 0; i < n; i ++)
    {
        long long a;
        scanf("%lld", &a);
        currentSum = max(a, currentSum + a);
        maxSum = max(maxSum, currentSum);
    }
    cout << maxSum << endl;
    return 0;
}