Maximum sum subarray
Given an array of
n
integers, find a contiguous subarray with the maximum sum of values. Input
The first line of the input contains an integer
n
- number of elements in the array (1 β€ n β€ ).The next line contains
n
integers separated by a space, that represent the elements of the array . Output
The program should print a single integer - the highest possible sum of the subarrays in the given array.
Examples
Input | Output |
9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
Explanation
- -2 1 -3
4 -1 3 1
-4 -2 β The sum of the highlighted subarray is (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7
-10 -20 4 β 3 + 4 -3 + 1 + 7 = 12
Β
Can you make this even better π?
Itβs possible to solve this problem without any additional arrays. Can you do that?
Β
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB