动态规划解决最大子段和问题需要的时间复杂度为 O(n)。是最好的一种解决办法。

设 b[j] 存储的是 A[i:j] 的最大字段和，其中 1 <= i <= j，再定义一个 sum 存储最终结果，那么：

当 b[j - 1] <= 0，b[j] = a[j]，即当目前子序列 A[i:j - 1] 的和为负数时，给和不停的赋新值，直到和为正。
当 b[j - 1] > 0，b[j] = b[j - 1] + a[j]，即当目前子序列 A[i:j - 1] 的和为正时，加上子序列中的下一个数，得到一个新的和 b[j]。
将 b[j] 和 sum 比较，若 b[j] > sum，那么给 sum 赋新值 b[j]；若 b[j] < sum，俺么保持 sum 值不变。通过这种方式来保持 sum 为子序列的最大值。

#include <iostream>

using namespace std;


const int N = 110;

int n;
int a[N];

int maxsum(int a[N], int n)
{
    int sum = 0;
    int b = 0;

    for(int i = 0; i < n; i ++)
    {
        if(b > 0)
        b += a[i];
        else b = a[i];

        if(b > sum) sum = b;
    }
    return sum;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)  cin >> a[i];
    cout << "最大连续子段和为" << maxsum(a, n) << endl;

    return 0;
}