Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Output

The maximum subarray sum.

Constraints

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

  1. Think about the best subarray that ends exactly at index i.
  2. 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);
    }
}

Solve Maximum Subarray Sum online · All practice problems