Max Consecutive Sum
MediumPractice library · +20 XPtwo pointersdynamic programminggreedy
Given an array of N integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer representing the maximum sum found.
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
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
The subarray [4, -1, 2, 1] has the largest sum = 6.
Example 2
Input
1 5
Output
5
The subarray [5] has the largest sum = 5.
Hints
Similar problems
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
- Longest Subarray with Constant DifferenceMedium
- Maximum Sum of Non-Overlapping Positive SubarraysMedium
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Maximum Sum of Consecutive SubsegmentsMedium
More topics: Two Pointers 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()
Example 1 input
9 -2 1 -3 4 -1 2 1 -5 4
Example 2 input
1 5