Maximum Sum of Non-Overlapping Subsegments
Given an array of N integers, find the maximum possible sum of a set of non-overlapping subsegments. You can choose to select zero subsegments, in which case the sum is 0. A subsegment is defined by its start and end indices (inclusive). Two subsegments are non-overlapping if they do not share any common elements.
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 non-overlapping subsegments.
Constraints
1 <= N <= 200000, -10^9 <= a_i <= 10^9
Example 1
9 1 -2 3 4 -1 2 1 -5 4
15
The optimal set of segments are [1], [3,4], [2,1], [4] with total sum 1 + 7 + 3 + 4 = 15.
Example 2
3 -1 -2 -3
0
Since all numbers are negative, the maximum sum is 0 by selecting no segments.
Hints
Similar problems
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Longest Alternating SubsequenceMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
- Maximum Sum of Non-overlapping SubarraysMedium
- Max Consecutive SumMedium
More topics: 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()
9 1 -2 3 4 -1 2 1 -5 4
3 -1 -2 -3