Maximum Subarray

NeetCode: Maximum Subarray · LeetCode: 53. Maximum Subarray · Difficulty: Medium

Given an integer array nums, find the contiguous non-empty subarray with the largest sum and return that sum.

Example

Text

Input:  nums = [2, -3, 4, -2, 2, 1, -1, 4]    Output: 8    (subarray [4, -2, 2, 1, -1, 4])
Input:  nums = [-2, -1]                       Output: -1

Brute force: every start, extend to every end

Fix a start index and extend the end one element at a time, keeping a running sum, and track the best sum seen. There are O(n^2) (start, end) pairs. Re-summing each subarray from scratch would cost O(n^3).

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int best = nums[0];
        for (int start = 0; start < nums.length; start++) {
            int sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                best = Math.max(best, sum);
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxSubArray(new int[]{2, -3, 4, -2, 2, 1, -1, 4}));
        System.out.println(s.maxSubArray(new int[]{-2, -1}));
        System.out.println(s.maxSubArray(new int[]{-5}));
    }
}

Output

8
-1
-5

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

Optimal: Kadane's algorithm

The best subarray ending at index i is either nums[i] alone or the best subarray ending at i - 1 extended by nums[i]. Extending helps only if the previous sum is positive; a negative prefix can only reduce the total, so it is dropped. An optimal subarray never needs a negative-sum prefix, so this choice is safe.

Keep cur = max(x, cur + x) and a global best.

x	cur	best
2	2	2
-3	-1	2
4	4	4
-2	2	4
2	4	4
1	5	5
-1	4	5
4	8	8

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0];
        int best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxSubArray(new int[]{2, -3, 4, -2, 2, 1, -1, 4}));
        System.out.println(s.maxSubArray(new int[]{-2, -1}));
        System.out.println(s.maxSubArray(new int[]{-5}));
    }
}

Output

8
-1
-5

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

cur and best start from nums[0] rather than 0, which keeps the answer correct when every number is negative, since the subarray must be non-empty.

The sums are int values, which wrap silently on overflow. Inputs with very large sums would need long.