Maximum Prefix Sum Difference
MediumPractice library · +20 XPprefix sumsarraymaximum
Given an array of N integers, find the maximum possible difference between two prefix sums. That is, find the maximum value of prefix_sum[j] - prefix_sum[i] for all 0 <= i <= j < N, where prefix_sum[k] is the sum of the first k+1 elements of the array (0-indexed). Assume prefix_sum[-1] = 0.
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer representing the maximum prefix sum difference.
Constraints
1 <= N <= 200000, -10^9 <= a[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 1 2 -3 4 -5
Output
4
Prefix sums are: 0, 1, 3, 0, 4, -1. Max difference is 4 (4 - 0).
Example 2
Input
4 -1 -2 -3 -4
Output
0
Prefix sums are: 0, -1, -3, -6, -10. Max difference is 0 (0 - 0).
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 -3 4 -5
Example 2 input
4 -1 -2 -3 -4