题目描述

最大字段和是容易处理的普及-问题
就是又堆了好多细节qwq

$O(n)$

C++ 代码

#include <iostream>
using namespace std;
const int N = 10010;
int a[N], f[N], n, res = -2e9;
int l, r;
int tl;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    bool is_neg = true;
    for (int i = 1; i <= n; i ++)
        if (a[i] >= 0) is_neg = false;
    if (is_neg)
    {
        cout << 0 << " " << a[1] << " " << a[n];
        return 0;
    }
    tl = l = a[1], r = a[n];
    for (int i = 1; i <= n; i ++)
    {
        f[i] = max(f[i - 1] + a[i], a[i]);
        if (f[i - 1] + a[i] < a[i]) tl = a[i];
        if (f[i] > res)
        {
            res = f[i];
            r = a[i];
            l = tl;
        }
    }
    cout << res << " " << l << " " << r;
}