最大子串和--动态规划经典问题

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/44080943

【问题描述】
在长度为N的整形数组中，求连续子串的和的最大值，要求复杂度为O(N)。
例如：1 2 3 -1 -20 100 34，结果为134。

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>

using namespace std;

int n, p[10010];

int main()
{
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
            cin >> p[i];
        int b = 0, sum = 0;

        for (int i = 0; i < n; i++)
        {
            b += p[i];
            if (b > sum)
                sum = b;
            if (b < 0)
                b = 0;
        }
        cout << sum << endl;
    }
    return 0;
}