Code Logo

Maximum Subarray

Published at24 Jul 2026
Created by
Medium 0 views
Like0

Given an integer array nums, find the contiguous subarray (containing at least one number) with the largest sum and return its sum. This is known as the Maximum Subarray problem and is solved optimally with Kadane's algorithm, a classic example of dynamic programming.

Kadane's algorithm maintains two variables: the maximum sum ending at the current position, and the maximum sum seen so far. At each position, we decide whether to extend the current subarray or start a new one. The decision is: maxEndingHere = max(nums[i], maxEndingHere + nums[i]). This captures the optimal subarray ending at each position.

The DP recurrence is straightforward: the maximum subarray ending at position i is either the element itself (starting fresh) or the element plus the maximum subarray ending at position i-1 (extending). The answer is the maximum across all positions. This runs in O(n) time with O(1) space.

Edge cases include a single element (return that element), all negative numbers (return the largest negative), and an array with zeros and positives interleaved.

Kadane's algorithm is a classic example of DP where the subproblem is the maximum subarray ending at each position. By extending the best previous subarray or starting fresh, the algorithm explores all possible subarrays implicitly without enumerating them.

Example Input & Output

Example 1
Input
[-1]
Output
-1
Explanation

Single negative element.

Example 2
Input
[5,4,-1,7,8]
Output
23
Explanation

Entire array sums to 23.

Example 3
Input
[-2,1,-3,4,-1,2,1,-5,4]
Output
6
Explanation

Subarray [4,-1,2,1] sums to 6.

Example 4
Input
[1]
Output
1
Explanation

Single element.

Example 5
Input
[1,2,3,4]
Output
10
Explanation

Entire array sums to 10.

Algorithm Flow

Recommendation Algorithm Flow for Maximum Subarray
Recommendation Algorithm Flow for Maximum Subarray

Solution Approach

Kadane's algorithm: track max sum ending here and max sum so far. Update both at each step.

function solution(nums) {
  var maxSoFar = nums[0];
  var maxEndingHere = nums[0];
  for (var i = 1; i < nums.length; i++) {
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

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

Best Answers

java
class Solution {
    public int solution(int[] nums) {
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
}