前后缀分离，类似题目：AcWing 1056. 股票买卖 III

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N], g[N], f[N];

int main()
{
    int T;
    cin >> T;

    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

        g[0] = -1e5;
        for (int i = 1, s = 0; i <= n; i ++ )   //从前往后算每个点以前的最大连续子序列
        {
            s = max(s, 0) + w[i];               //贪心算法，只要前缀和小于0就丢弃
            g[i] = max(s, g[i - 1]);
        }

        f[n + 1] = -1e5;
        for (int i = n, s = 0; i; i -- )        //从后往前算每个点以后的最大连续子序列
        {
            s = max(s, 0) + w[i];
            f[i] = max(s, f[i + 1]);
        }

        int res = -1e5;
        for (int i = 1; i < n; i ++ )           //以当前点为分割点的最大连续子序列
        {                                       // = 左边的最大连续子序列+右边的最大连续子序列
            res = max(res, g[i] + f[i + 1]);
        }

        printf("%d\n", res);
    }

    return 0;
}