一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1903C - Theofanis' Nightmare

---

二、解题报告

1、思路分析

我们任意一种分组其实都是若干个后缀和相加

比如我们分成了三组，第一组的数被加了一次，第二组的数被加了两次，第三组的数被加了三次

加入nums[0, 3]为第一组，nums[4, 5]为第二组，nums[6, 7]为第三组，后缀和acc[i]代表从i开始的后缀和

那么相当于acc[0] + acc[4] + acc[6]

那我们预处理后缀和只要大于0就加就行了

为了保证合法性，必须加一下整个数组和

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

 ​

import heapq
import sys
from collections import Counter
from collections import deque
from itertools import accumulate

input = lambda: sys.stdin.readline().strip()
MII = lambda: map(int, input().split())
LMI = lambda: list(map(int, input().split()))
I = lambda: int(input())
fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
P = 998244353

def main():
        n = I()
        a = LMI()
        acc = list(accumulate(a[::-1]))
        res = acc[-1]
        for i in range(n - 2, -1, -1):
            if acc[i] > 0:
                res += acc[i]
        print(res)

if __name__ == '__main__':
    T = I()
    for _ in range(T):
        main();