Maximum Sum of Non-Overlapping Positive Subarrays
Given an array of N integers, find the maximum possible sum of elements that can be obtained by selecting a set of non-overlapping subarrays. Each selected subarray must have a positive sum.
Input
The first line contains an integer N. The second line contains N space-separated integers a_1, a_2, ..., a_N.
Output
Print a single integer, the maximum sum achievable.
Constraints
1 <= N <= 200000 -10^9 <= a_i <= 10^9
Example 1
5 1 -2 3 4 -1
8
We can select subarray [1] (sum 1) and subarray [3, 4] (sum 7). They are non-overlapping. Total sum = 1 + 7 = 8. The greedy algorithm sums: [1] -> total=1, reset; [-2] -> reset; [3] -> sum=3, total=1+3=4, reset; [4] -> sum=4, total=4+4=8, reset; [-1] -> reset. Final sum = 8.
Example 2
3 -1 -2 -3
0
No subarray has a positive sum. The maximum sum achievable is 0.
Hints
Similar problems
- Longest Increasing Subsequence with Stack ConstraintHard
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
- Maximum Sum of Consecutive SubsegmentsMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
More topics: Greedy problems, Dynamic Programming problems, Stack problems
# 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 -1
3 -1 -2 -3