Max Difference Between Two Prefix Sums
Given an array $A$ of $N$ integers, find the maximum possible value of $P[j] - P[i]$ for all $0 \le i < j < N$, where $P$ is the prefix sum array of $A$ (i.e., $P[k] = A[0] + A[1] + \dots + A[k]$). If no such pair $i < j$ exists, output 0.
Input
The first line contains an integer $N$. The second line contains $N$ space-separated integers $A_0, A_1, \dots, A_{N-1}$.
Output
Print a single integer, the maximum difference $P[j] - P[i]$ for $i < j$. If the array has size 0 or 1, print 0.
Constraints
1 \le N \le 200000; -10^9 \le A_i \le 10^9
Example 1
5 1 2 -3 4 5
9
Prefix sums are [1, 3, 0, 4, 9]. Max difference is P[4] - P[2] = 9 - 0 = 9.
Example 2
3 -1 -2 -3
0
Prefix sums are [-1, -3, -6]. Max difference is P[1] - P[0] = -3 - (-1) = -2. Since we want P[j]-P[i] where i<j, and we want to maximize this, we must have P[j] > P[i]. If all differences P[j]-P[i] are negative, the maximum is the least negative one. However, the problem statement implies we're look
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 -3 4 5
3 -1 -2 -3