题目描述

blablabla

样例

不是题解，自己复习用，请谅解！

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 50010;
int l[N], r[N];
int nums[N], T;

int main()
{
    cin >> T;
    while (T --)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i  < n; i ++) scanf("%d", &nums[i]);

        l[0] = nums[0];
        int s = nums[0];
        for (int i = 1; i < n; i ++)
        {
            s = nums[i] + max(0, s);
            l[i] = max(l[i - 1], s);
        }

        r[n - 1] = nums[n - 1];
        s = nums[n - 1];
        for (int i = n - 2; i >= 0; i --)
        {
            s = nums[i] + max(0, s);
            r[i] = max(r[i + 1], s);
        }

        int res = -0x3f3f3f3f;
        for (int i = 0; i < n - 1; i ++) res = max(res, l[i] + r[i + 1]);

        cout << res << endl;
    }

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla