Code Logo

Maximum Subarray

Published at24 Jul 2026
Created by
Medium 2 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

Solution Approach

Find the maximum sum of a contiguous subarray using Kadane's algorithm. The key insight is that at each position, the maximum subarray ending at that position is either the element itself or the element plus the maximum subarray ending at the previous position. Track a running sum and reset it to 0 when it becomes negative, because a negative prefix would only reduce any future sum.

function maxSubArray(nums) {
  var maxSum = nums[0], curSum = 0;
  for (var i = 0; i < nums.length; i++) {
    curSum += nums[i];
    if (curSum > maxSum) maxSum = curSum;
    if (curSum < 0) curSum = 0;
  }
  return maxSum;
}

Kadane's algorithm works because a subarray with a negative sum cannot be part of the maximum subarray — discarding it and starting fresh from the next element is always optimal. The maxSum variable tracks the best result seen globally.

Time complexity is O(n), space complexity is 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;
    }
}