Rating System (Codeforces 1845D)
Tags: Math, dsu

You are developing a rating system for an online game. Every time a player participates in a match, the player's rating changes depending on the results.Initially, the player's rating is $$$0$$$. There are $$$n$$$ matches; after the $$$i$$$-th match, the rating change is equal to $$$a_i$$$ (the rating increases by $$$a_i$$$ if $$$a_i$$$ is positive, or decreases by $$$|a_i|$$$ if it's negative. There are no zeros in the sequence $$$a$$$).The system has an additional rule: for a fixed integer $$$k$$$, if a player's rating has reached the value $$$k$$$, it will never fall below it. Formally, if a player's rating at least $$$k$$$, and a rating change would make it less than $$$k$$$, then the rating will decrease to exactly $$$k$$$.Your task is to determine the value $$$k$$$ in such a way that the player's rating after all $$$n$$$ matches is the maximum possible (among all integer values of $$$k$$$). If there are multiple possible answers, you can print any of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of matches.The second line contains $$$n$$$ integer $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$; $$$a_i \ne 0$$$) — the rating change after the $$$i$$$-th match.The sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print one integer $$$m$$$ ($$$-10^{18} \le m \le 10^{18}$$$) — the value of $$$k$$$ such that the rating of the player will be the maximum possible when using this value. It can be shown that at least one of the optimal answers meets the constraint $$$-10^{18} \le m \le 10^{18}$$$.

Note: In the first example, if $$$k=3$$$, then the rating changes as follows: $$$0 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 6$$$.In the second example, if $$$k=0$$$, then the rating changes as follows: $$$0 \rightarrow 0 \rightarrow 0 \rightarrow 0$$$.In the third example, if $$$k=25$$$, then the rating changes as follows: $$$0 \rightarrow 4 \rightarrow 6$$$.In the fourth example, if $$$k=6$$$, then the rating changes as follows: $$$0 \rightarrow 5 \rightarrow 6 \rightarrow 6 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 8$$$.

Sample Inputs:
4
4
3 -2 1 2
3
-1 -2 -1
2
4 2
7
5 1 -3 2 -1 -2 2

Sample Outputs:
3
0
25
6

Solution (Python):
import sys
import math
from collections import defaultdict
import bisect as bs
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a = [0] + a
    if all((a[i] > 0 for i in range(n))):
        return 1
    if all((a[i] < 0 for i in range(n))):
        return 0
    curr = 0
    best = math.inf
    bi = None
    ci = 0
    for (i, ai) in enumerate(a):
        if ai < curr + ai:
            ci = i
            curr = ai
        else:
            curr += ai
        if curr < best:
            best = curr
            bi = ci
    return sum(a[:bi])
t = int(input())
for _ in range(t):
    res = solve()
    print(res)

Solution (Python):
B = input
for C in range(int(B())):
    B()
    sum = 0
    D = 0
    E = 0
    A = 0
    for C in list(map(int, B().split())):
        sum += C
        if sum > A:
            A = sum
        if A - sum > E:
            E = A - sum
            D = A
    print(D)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    changes = map(int, input().split(' '))
    largestNeg = 0
    curNeg = 0
    markRating = 0
    curRating = 0
    for change in changes:
        curNeg += change
        curRating += change
        if curNeg > 0:
            curNeg = 0
        if curNeg < largestNeg:
            markRating = curRating - curNeg
            largestNeg = curNeg
    print(markRating)