Particles (Codeforces 1844C)
Tags: Math, dp

You have discovered $$$n$$$ mysterious particles on a line with integer charges of $$$c_1,\dots,c_n$$$. You have a device that allows you to perform the following operation:   Choose a particle and remove it from the line. The remaining particles will shift to fill in the gap that is created. If there were particles with charges $$$x$$$ and $$$y$$$ directly to the left and right of the removed particle, they combine into a single particle of charge $$$x+y$$$. For example, if the line of particles had charges of $$$[-3,1,4,-1,5,-9]$$$, performing the operation on the $$$4$$$th particle will transform the line into $$$[-3,1,9,-9]$$$.  If we then use the device on the $$$1$$$st particle in this new line, the line will turn into $$$[1,9,-9]$$$. You will perform operations until there is only one particle left. What is the maximum charge of this remaining particle that you can obtain?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$c_1,\dots,c_n$$$ ($$$-10^9 \le c_i \le 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output one integer, the maximum charge of the remaining particle.

Note: In the first test case, the best strategy is to use the device on the $$$4$$$th particle, then on the $$$1$$$st particle (as described in the statement), and finally use the device on the new $$$3$$$rd particle followed by the $$$1$$$st particle.In the second test case, the best strategy is to use the device on the $$$4$$$th particle to transform the line into $$$[998244353,998244353,1996488706]$$$, then on the $$$2$$$nd particle to transform the line into $$$[2994733059]$$$. Be wary of integer overflow.In the third test case, there is only one particle, so no operations can be performed.

Sample Inputs:
3
6
-3 1 4 -1 5 -9
5
998244353 998244353 998244353 998244353 998244353
1
-2718

Sample Outputs:
9
2994733059
-2718

Solution (Python):
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
    MNR = int(input())
    L = list(map(int, input().split()))
    Res = max(L)
    if Res < 0:
        print(Res)
    else:
        print(max(sum([li for li in L[::2] if li > 0]), sum([li for li in L[1::2] if li > 0])))

Solution (Python):
import sys

def particles(n, arr):
    even_sum = 0
    odd_sum = 0
    for i in range(n):
        if i % 2 == 0:
            if arr[i] >= 0:
                even_sum += arr[i]
        elif arr[i] >= 0:
            odd_sum += arr[i]
    if even_sum == 0 and odd_sum == 0:
        return max(arr)
    else:
        return max(even_sum, odd_sum)
test = int(sys.stdin.readline())
for _ in range(test):
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    ans = particles(n, arr)
    print(ans)

Solution (Python):
from sys import stdin as input
t = int(input.readline())
for _ in range(t):
    n = int(input.readline())
    p = list(map(int, input.readline().split()))
    if n == 1:
        print(p[0])
    else:
        p_odd = sum([p[i] for i in range(0, n, 2) if p[i] > 0])
        p_even = sum([p[i] for i in range(1, n, 2) if p[i] > 0])
        if p_odd == 0 and p_even == 0:
            max_odd = max([p[i] for i in range(0, n, 2)])
            max_even = max([p[i] for i in range(1, n, 2)])
            print(max(max_odd, max_even))
        else:
            print(max(p_odd, p_even))