『算法-ACM 竞赛-动态规划』经典算法-最大子段和

状态转移方程：

f[i]=max(a[i],f[i-1]+a[i])    //要么舍弃，要么累加
即：前端序列小于0舍去，前子段大于0，不要白不要，加上！

#include <bits/stdc++.h>
using namespace std;
//---------------https://lunatic.blog.csdn.net/-------------------//
int data[100000];
int maxsum(int *a, int ln)
{
    int maxi = 0, ans = 0;
    for (int i = 1; i <= ln; i++)
    {
        if (maxi < 0)
            maxi = data[i];
        else maxi+=data[i];
        ans = max(ans, maxi);
    }
    return ans;
}
int main()
{
    int len;
    cin >> len;
    for (int i = 1; i <= len; i++)
        cin >> data[i];
    cout << maxsum(data, len);
}