Maximum Sum of Consecutive Subsegments
Given an array of N integers, find the maximum possible sum of a non-empty contiguous subsegment. A contiguous subsegment is defined by its start and end indices (inclusive). If multiple subsegments yield the same maximum sum, choose the shortest one. If there are still multiple shortest subsegments, choose the one with the smallest starting index.
Input
The first line contains an integer N. The second line contains N integers, representing the elements of the array.
Output
Print a single integer, the maximum sum of a contiguous subsegment.
Constraints
1 <= N <= 200000 -10^9 <= A[i] <= 10^9
Example 1
5 1 -2 3 4 -1
7
The subsegment [3, 4] has sum 7. It's the maximum sum. Indices are 2 to 3. Length is 2. Start is 2.
Example 2
3 -1 -2 -3
-1
The subsegment [-1] has sum -1. It's the maximum sum. Indices are 0 to 0. Length is 1. Start is 0.
Hints
Similar problems
- Maximum Sum of Non-Adjacent SubarraysMedium
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Max Consecutive SumMedium
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Longest Alternating SubsequenceMedium
- Maximum Sum of Non-overlapping SubarraysMedium
More topics: Arrays 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()
5 1 -2 3 4 -1
3 -1 -2 -3