Maximum Subarray (Kadane's Algorithm)

Given an array of integers, find the contiguous subarray (at least one element) with the largest sum, and return that sum.

LeetCode: 53. Maximum Subarray

Example 1

Text

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: the subarray [4, -1, 2, 1] has the largest sum.

Example 2

Text

Input:  [-3, -1, -2]
Output: -1
Explanation: every subarray is negative. The best is the single element [-1].

Brute force: try every subarray

The simplest version tries every start i and end j and sums nums[i..=j] from scratch, which is O(n³). Keeping a running sum while j moves right removes the innermost loop:

Java

public class Main {
    static int maxSubarray(int[] nums) {
        int best = Integer.MIN_VALUE;
        for (int start = 0; start < nums.length; start++) {
            int sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];            // sum of nums[start..=end]
                best = Math.max(best, sum);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxSubarray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(maxSubarray(new int[]{-3, -1, -2}));
    }
}

Output

6
-1

Time: O(n²). Space: O(1).

Optimal: Kadane's algorithm

Let current be the best sum of a subarray that ends at the current index. When moving to the next element x, there are only two choices:

Extend the best subarray ending at the previous index: current + x.
Start a new subarray at x: x.

Take the larger one: current = max(x, current + x). Starting fresh wins exactly when current has become negative, because a negative prefix only makes any later sum smaller. The answer is the largest current seen at any index.

Walkthrough with [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

x	extend (current + x)	start fresh (x)	current	best
-2			-2	-2
1	-1	1	1	1
-3	-2	-3	-2	1
4	2	4	4	4
-1	3	-1	3	4
2	5	2	5	5
1	6	1	6	6
-5	1	-5	1	6
4	5	4	5	6

Java

public class Main {
    static int maxSubarray(int[] nums) {
        int current = nums[0];
        int best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            current = Math.max(nums[i], current + nums[i]);
            best = Math.max(best, current);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxSubarray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(maxSubarray(new int[]{-3, -1, -2}));
        System.out.println(maxSubarray(new int[]{5}));
    }
}

Output

6
-1
5

Time: O(n). Space: O(1).

Starting current and best at nums[0] (instead of 0) is what makes the all-negative case return -1 instead of 0. 0 would be the sum of an empty subarray, which the problem does not allow. The method assumes nums is not empty, as the problem guarantees. On an empty array, nums[0] throws ArrayIndexOutOfBoundsException. If empty input is possible, return OptionalInt (a container that holds one int or nothing).

Returning where the subarray is

Interviewers often ask for the subarray itself. Remember where the current run started, and save the range whenever best improves. The method returns an int[] of three values: the sum, the start index, and the end index (exclusive).

Java

import java.util.Arrays;

public class Main {
    static int[] maxSubarrayRange(int[] nums) {
        int current = nums[0], best = nums[0];
        int start = 0, bestStart = 0, bestEnd = 1;
        for (int i = 1; i < nums.length; i++) {
            if (current + nums[i] < nums[i]) {
                current = nums[i];
                start = i; // start a new run here
            } else {
                current += nums[i];
            }
            if (current > best) {
                best = current;
                bestStart = start;
                bestEnd = i + 1;
            }
        }
        return new int[]{best, bestStart, bestEnd};
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] r = maxSubarrayRange(nums);
        System.out.println(r[0] + " " + r[1] + ".." + r[2] + " "
                + Arrays.toString(Arrays.copyOfRange(nums, r[1], r[2])));
    }
}

Output

6 3..7 [4, -1, 2, 1]

Edge cases

Single element: the answer is that element.
All negative: the answer is the largest single element.
Overflow: long arrays of large values can overflow int and wrap silently. Use long for current and best if the constraints allow it.