Coding Interview PatternsMaximum Subarray
MediumGreedy Techniques

Maximum Subarray

Explanation & Solution

Practice Problem

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Input:nums = [-2,1,-3,4,-1,2,1,-5,4]
0
-2
1
1
2
-3
3
4
4
-1
5
2
6
1
7
-5
8
4

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Approach

Greedy Techniques pattern

1. Initialize Tracking Variables

  • Set currentSum to nums[0] — this tracks the maximum subarray sum ending at the current position.
  • Set maxSum to nums[0] — this tracks the overall maximum subarray sum found so far.
  • We initialize both to the first element rather than 0 because the array could contain all negative numbers.

2. Iterate Through the Array

  • Starting from index 1, examine each element one at a time.
  • At each position, we make a decision: should we extend the previous subarray or start a new one here?

3. Decide: Extend or Start Fresh

  • Compute currentSum = Math.max(nums[i], currentSum + nums[i]).
  • If currentSum + nums[i] is greater than nums[i] alone, the previous subarray is still contributing positively, so we extend it.
  • If nums[i] alone is larger, the accumulated sum has become a burden (negative), so we discard it and start a new subarray from the current element.

4. Update the Global Maximum

  • After updating currentSum, compare it with maxSum.
  • If currentSum > maxSum, update maxSum to currentSum.
  • This ensures we never lose track of the best subarray encountered at any point during the scan.

5. Return the Result

  • After processing all elements, maxSum holds the largest subarray sum.
  • This works correctly even when all elements are negative — it will return the least negative (largest) single element.

Key Insight

  • This is Kadane's Algorithm. The core insight is that at each position, the maximum subarray ending here is either the current element alone or the current element plus the best subarray ending at the previous position. If the running sum ever becomes negative, it can only drag down future sums, so we reset by starting fresh from the current element.
Time
O(n)a single pass through the array.
Space
O(1)only two variables are maintained.

Visualization

Input:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
-2011-3243-142516-5748
—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone
10 steps

Solution Code

Previous
Reorganize String
Next
Hand of Straights