最大子段和

给定一个长度为 \(n\) 的序列，请求出连续子序列的最大值。

输入格式

第一行输入一个正整数 \(n\)

第二行输入 \(n\) 个整数，可能为负数

输出格式

输出一个整数代表连续子序列和的最大值。

思路

假设该最优的连续子段为 \([i, j]\)，那么该子段多一个元素，少一个元素都不可以:

\([i + 1, j] < [i, j]\)
\([i, j + 1] < [i, j]\)
\([i - 1, j] < [i, j]\)
\([i, j - 1] < [i, j]\)

并且对于任意的 \(i \leq k \leq j\) 来说，\([i, k]\) 和 \([k, j]\) 都不可能为负，不然我可以丢弃这部分值会变的更大；

若题目给的序列全是正整数，那么最大值就是序列总和；

如果序列全是负数，那么最大值就是该序列的最大元素值。

如果是正整数和负数混合的情况下，我要不断的维护一个窗口 \([i, j]\) ，如果 \(j++\) 吞并右边的元素，窗口总和为负数了，那么最优子段一定不包含这部分，窗口的起点要从 \(j + 1\) 开始；否则就继续吞并。

代码参考

#include <iostream>

using namespace std;
typedef long long LL;
const int N = 1e7 + 10;

// &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& //

// 最优的连续区间，多一个不行，少一个也不行
// 如果全部正整数，答案就是总和
// 假设该区间为 [i, j] 则 [i + 1, j] < [i, j] 且 [i, j + 1] < [i, j]
// 并且 [i, j] 内对于任意的 [i, k] 或者 [k, j] 都必定是正整数，不然的话我丢弃这部份岂不是更大？
// 想象一下区间吞并，不断的吞并右边的数，如果吞并后的和为负数，说明此时最大的连续只能是 [i, j - 1] 为了寻找下一段连续区间 i 要移动到 j 处

LL n, res, i, j, sum;
LL a[N];

void solve()
{
    cin >> n;
    for (i = 1; i <= n; i ++) cin >> a[i];
    i = j = 1, sum = 0; res = 1 << 31;
    while (j <= n)
    {
        res = max(res, a[j]);
        if (sum + a[j] >= 0) res = max(res, sum += a[j ++]);
        else sum = 0, i = j = j + 1;
    }
    cout << res << endl;
}

// &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& //

int main(void)
{
    solve(); return 0;
}