题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(-10^8 \leq a[i] \leq 10^8)$。

你需要把$a$分割成若干非空段，假设分割成了$k$段，那么得分为：

第一段的元素和$\times 1+$第二段的元素和$\times 2+…+$第$k$段的元素和$\times k$

例如$[1,2,3,4]$分成两段$[1,2]$和$[3,4]$，得分为$(1+2) \times 1 + (3+4) \times 2$

输出最大得分。

输入样例

4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830

输出样例

32
4
343
830

算法

后缀和

本质上题目所给的操作就是找一些后缀和累加起来（并且第一个后缀和$s_1=\Sigma_{i=1}^{n}a[i]$是必选的），使得这个累加和最大。

下面解释一下为什么是选一些后缀相加，因为第$k$个后缀其实是第$k-1$个后缀的后缀，所以在加过第$k$个后缀的情况下，再把第$k-1$个后缀加上去就相当于第$k$个后缀加了两次的。因此，第$k-1$个后缀中不在第$k$个后缀中的元素就只加了一次，这样就相当于前面一个子数组加了一次，后面一个子数组加了两次。依此类推累加到第一个后缀，就能得到题目想要求的东西。

那么我们找到除了$s_1$之外所有大于$0$的后缀加起来就可以了，它就是题目要求的最大累加和。

复杂度分析

时间复杂度

遍历一遍数组就可以求得答案，因此时间复杂度为$O(n)$。

空间复杂度

除了输入的原始数组$a$，仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, a[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        LL sufsum = 0, ans = 0;
        for(int i = n; i >= 1; i--) {
            sufsum += a[i];
            if(i > 1 && sufsum > 0) {
                ans += sufsum;
            }
        }
        ans += sufsum;
        printf("%lld\n", ans);
    }
    return 0;
}