Maximum Sum of Non-overlapping Subarrays
Given an array of N integers, find the maximum possible sum of elements from a set of non-overlapping subarrays. A subarray is a contiguous part of the array. Two subarrays are non-overlapping if they do not share any common elements. For example, if the array is [1, 2, 3, 4, 5], subarrays [1, 2] and [4, 5] are non-overlapping, but [1, 2] and [2, 3] are overlapping.
Input
The first line contains an integer N. The second line contains N space-separated integers, the elements of the array.
Output
Print a single integer: the maximum possible sum of elements from a set of non-overlapping subarrays.
Constraints
1 <= N <= 200000 -10^9 <= A[i] <= 10^9
Example 1
6 1 -2 3 4 -1 2
10
The non-overlapping subarrays [3, 4] (sum 7) and [2] (sum 2) yield a total sum of 9. This is the maximum possible.
Example 2
5 -1 -2 -3 -4 -5
0
All elements are negative. No subarray has a positive sum. The maximum sum achievable is 0 (by selecting no subarrays).
Hints
Similar problems
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
- Maximum Sum of Non-Overlapping Positive SubarraysMedium
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Maximum Sum of PairsMedium
More topics: Prefix Sums problems, Greedy problems, Dynamic Programming problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
6 1 -2 3 4 -1 2
5 -1 -2 -3 -4 -5