返回 01-复杂度2 Maximum Subsequence Sum (25分) 翻译+题解

代码很详细

#include <iostream>
using namespace std;
const int MAX_N = 1e4 + 10;
int main()
{
    int start, end, sum;
    int x[MAX_N];
    int temp;
    int n;
    cin >> n;
    sum = end = start = temp = 0;
    //maxt初始化为-1 能避免
    //全是负数
    // 负数和0
    int maxt = -1;
    for (int i = 0; i < n; ++i)
    {
        cin >> x[i];
        sum += x[i];
        //找到新的 子序列
        if (sum > maxt)
        {
            maxt = sum;
            //记录开头和结尾
            start = temp;
            end = i;
        }
        //sum<0 是一个新的开始
        else if (sum < 0 && i < n - 1)
        {
            //刷新sum
            sum = 0;
            //记录开头
            temp = i + 1;
        }
        //到最后还是负数
        else if (maxt < 0 && i == n - 1)
        {
            maxt = 0;
            start = 0;
            end = n - 1;
        }
    }
    cout << maxt << ' ' << x[start] << ' ' << x[end];
    return 0;
}