Maximum Subarray

Medium Problem 12 of 151 Java and Python

Practice on LeetCode

Problem

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

Example 1

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Why: The subarray [4, -1, 2, 1] adds up to 6.

Example 2

Input: nums = [5, 4, -1, 7, 8]
Output: 23
Why: The whole array.

Example 3

Input: nums = [-3, -1, -2]
Output: -1
Why: The subarray must not be empty, so pick the largest single number.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Explanation

Look at the best subarray that ends at index i. It either extends the best subarray ending at i - 1, or starts fresh at i. Extending only helps when that earlier sum is positive.

That one decision per element is Kadane's algorithm: keep a running sum, and drop it whenever it would drag the next element down.

Approach 1 · Naive

Every subarray

Time O(n²)
Space O(1)

Fix a start, extend the end one element at a time while keeping a running sum, and record the best.

For each start i, set sum = 0.
For each end j ≥ i, add nums[j] to sum and update best.

Java

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

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best = float("-inf")
        for i in range(len(nums)):
            total = 0
            for j in range(i, len(nums)):
                total += nums[j]
                best = max(best, total)
        return best

Approach 2 · Optimal

Kadane's algorithm

Time O(n)
Space O(1)

Carry the best sum of a subarray ending at the current index: either the element alone or the element added to the previous best.

Set current = best = nums[0].
For each later element x: current = max(x, current + x).
Update best = max(best, current).

Java

class Solution {
    public 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;
    }
}

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current = best = nums[0]
        for x in nums[1:]:
            current = max(x, current + x)
            best = max(best, current)
        return best

Complexity compared

Approach	Time	Space
Naive Every subarray	O(n²)	O(1)
Optimal Kadane's algorithm	O(n)	O(1)

Key takeaways

Start from nums[0], not 0, or an all-negative array returns the wrong answer.
"Best subarray ending here" is a pattern you will reuse in Maximum Product Subarray.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem