Practice › Arrays
Maximum Subarray Sum
Medium · Arrays · Asked at Amazon, Microsoft, Google, Flipkart, Paytm
Find the largest possible sum of a non-empty contiguous subarray.
Input
- First line:
n - Second line:
nintegers
Output
The maximum subarray sum.
Constraints
- 1 ≤ n ≤ 10^5
- -10^4 ≤ a[i] ≤ 10^4
Hint: Kadane's algorithm solves this in O(n).
Example 1
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
Example 2
Input
5 5 4 -1 7 8
Output
23
Hints
- Think about the best subarray that ends exactly at index i.
- Kadane: it is either a[i] alone or a[i] added to the best subarray ending at i − 1.
Approach
Kadane's algorithm keeps cur, the best sum of a subarray ending at the current index: cur = max(a[i], cur + a[i]). In other words, extend the previous subarray if it helps, otherwise start over. The answer is the largest cur seen. Starting best from a[0] (not 0) handles arrays where every value is negative.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long x, cur, best;
cin >> x;
cur = best = x;
for (int i = 1; i < n; i++) {
cin >> x;
cur = max(x, cur + x);
best = max(best, cur);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : data[0] + 1]
cur = best = a[0]
for x in a[1:]:
cur = max(x, cur + x)
best = max(best, cur)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long cur = sc.nextLong(), best = cur;
for (int i = 1; i < n; i++) {
long x = sc.nextLong();
cur = Math.max(x, cur + x);
best = Math.max(best, cur);
}
System.out.println(best);
}
}