Maximums (Codeforces 1326B)
Tags: Math, implementation

Alicia has an array, $$$a_1, a_2, \ldots, a_n$$$, of non-negative integers. For each $$$1 \leq i \leq n$$$, she has found a non-negative integer $$$x_i = max(0, a_1, \ldots, a_{i-1})$$$. Note that for $$$i=1$$$, $$$x_i = 0$$$.For example, if Alicia had the array $$$a = \{0, 1, 2, 0, 3\}$$$, then $$$x = \{0, 0, 1, 2, 2\}$$$.Then, she calculated an array, $$$b_1, b_2, \ldots, b_n$$$: $$$b_i = a_i - x_i$$$.For example, if Alicia had the array $$$a = \{0, 1, 2, 0, 3\}$$$, $$$b = \{0-0, 1-0, 2-1, 0-2, 3-2\} = \{0, 1, 1, -2, 1\}$$$.Alicia gives you the values $$$b_1, b_2, \ldots, b_n$$$ and asks you to restore the values $$$a_1, a_2, \ldots, a_n$$$. Can you help her solve the problem?

Input: The first line contains one integer $$$n$$$ ($$$3 \leq n \leq 200\,000$$$) – the number of elements in Alicia's array.The next line contains $$$n$$$ integers, $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$).It is guaranteed that for the given array $$$b$$$ there is a solution $$$a_1, a_2, \ldots, a_n$$$, for all elements of which the following is true: $$$0 \leq a_i \leq 10^9$$$.

Output: Print $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$), such that if you calculate $$$x$$$ according to the statement, $$$b_1$$$ will be equal to $$$a_1 - x_1$$$, $$$b_2$$$ will be equal to $$$a_2 - x_2$$$, ..., and $$$b_n$$$ will be equal to $$$a_n - x_n$$$.It is guaranteed that there exists at least one solution for the given tests. It can be shown that the solution is unique.

Note: The first test was described in the problem statement.In the second test, if Alicia had an array $$$a = \{1000, 1000000000, 0\}$$$, then $$$x = \{0, 1000, 1000000000\}$$$ and $$$b = \{1000-0, 1000000000-1000, 0-1000000000\} = \{1000, 999999000, -1000000000\}$$$.

Sample Inputs:
5
0 1 1 -2 1

3
1000 999999000 -1000000000

5
2 1 2 2 3

Sample Outputs:
0 1 2 0 3

1000 1000000000 0

2 3 5 7 10

Solution (Python):
n = int(input())
arr = [int(a) for a in input().split()]
ans = [arr[0]]
max_till_now = arr[0]
x = [0, max_till_now]
for i in range(1, n):
    a_i = arr[i] + max_till_now
    if max_till_now < a_i:
        max_till_now = a_i
    ans.append(a_i)
print(' '.join([str(j) for j in ans]))

Solution (Python):
n = int(input())
b = [int(elem) for elem in input().split()]
a = [0] * n
a[0] = b[0]
max_elem = a[0]
for i in range(1, n):
    a[i] = max_elem + b[i]
    max_elem = max(a[i], max_elem)
print(' '.join([str(elem) for elem in a]))

Solution (Python):
import math

def main():
    print(case())

def case():
    n = int(input())
    b = list(map(int, input().split()))
    a = []
    a.append(abs(b[0]))
    m = b[0]
    for i in range(1, n):
        a.append(m + b[i])
        if a[-1] > m:
            m = a[-1]
    return ' '.join(map(str, a))
main()