53. Maximum Subarray

Quick Identifier

• Topic: arrays-hashing
• Pattern: Kadane's Algorithm (Greedy / DP-1D)
• Hint: Does adding the current number to your running total make your situation worse than just starting a brand new running total from the current number itself?
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, LinkedIn
• LeetCode: 53

Quick Sights

• Time Complexity: O(n). We iterate through the array exactly once.
• Space Complexity: O(1). We only maintain two integer variables (currentSum and maxSum).
• Core Mechanism: As you iterate, maintain a running currentSum. For every new element, you have a greedy choice: either add the element to your existing currentSum, or throw away the currentSum entirely and start a new sum beginning with this element. You make this choice by checking which option yields a higher value. Keep track of the maxSum seen at any point.

Concept Explanation

As a senior engineer, Kadane's algorithm is the canonical example of dynamic programming collapsed into a greedy choice.

1. The Toxic Asset: Imagine you are acquiring assets (the numbers in the array). Some are profitable (positive), some are toxic debt (negative).
2. The Clean Slate: If your running total of assets ever drops below 0, your entire collection has become a net liability. If the next number in the array is 5, why would you add it to a negative running total (e.g., -2 + 5 = 3)? You are instantly better off throwing away all previous assets, declaring bankruptcy, and just taking the 5 by itself (0 + 5 = 5).
3. The Core Invariant: At index i, the maximum subarray sum ending exactly at i is either the element nums[i] by itself, or nums[i] added to the maximum subarray sum ending at i-1. currentSum = Math.max(nums[i], currentSum + nums[i])

Diagram

This flowchart outlines the greedy decision matrix of Kadane's Algorithm.

Study Pattern (SDE3+)

• 0–3 min: Recognize Kadane's instantly. It is the definitive $O(n)$ time / $O(1)$ space solution. Write out the recurrence relation dp[i] = max(nums[i], dp[i-1] + nums[i]) and explain how you optimize away the dp array into a single currentSum integer.
• Implementation pass: Initialize both currentSum and maxSum to nums[0]. Do not initialize them to 0, because if the array contains entirely negative numbers (e.g., [-3, -5, -2]), initializing to 0 will incorrectly return 0 instead of -2.
• 5 min extension: What if the interviewer asks you to return the start and end indices of the maximum subarray, not just the sum? You would track two extra variables: tempStart and bestStart. Whenever currentSum resets to value, you set tempStart = index. Whenever maxSum is updated, you set bestStart = tempStart and bestEnd = index.

Approaches

• Brute force — Check the sum of every possible subarray. Time: $O(n^2)$ (or $O(n^3)$ if implemented very naively). Space: $O(1)$.
• Divide and Conquer — Split the array in half, find the max in the left, max in the right, and max crossing the middle. Time: $O(n \log n)$, Space: $O(\log n)$ call stack. This is rarely the desired answer, but it's a common follow-up question.
• Kadane's Algorithm — DP optimized to $O(1)$ space. Time: $O(n)$, Space: $O(1)$. (Always pick this)

Optimal Solution

Go

func maxSubArray(nums []int) int {
	currentSum := nums[0]
	maxSum := nums[0]

	for i := 1; i < len(nums); i++ {
		value := nums[i]

		// Greedy choice: extend the existing subarray, or start a new one?
		if currentSum+value > value {
			currentSum += value
		} else {
			currentSum = value
		}

		// Update the global maximum if necessary
		if currentSum > maxSum {
			maxSum = currentSum
		}
	}

	return maxSum
}

JavaScript

function maxSubArray(nums) {
	let currentSum = nums[0];
	let maxSum = nums[0];

	for (let i = 1; i < nums.length; i++) {
		const value = nums[i];

		// Math.max succinctly expresses the greedy choice
		currentSum = Math.max(value, currentSum + value);
		maxSum = Math.max(maxSum, currentSum);
	}

	return maxSum;
}

Walkthrough

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6 (coming from subarray [4, -1, 2, 1])

Edge Cases

• All negative numbers (e.g., [-3, -5, -2]). Will correctly return -2.
• Single element array. Will correctly return that element.
• All positive numbers. Will naturally sum the entire array.

Pitfalls

• Initializing maxSum = 0. This completely breaks if the array contains only negative numbers. Always initialize to nums[0].
• Attempting a sliding window with a left pointer. Kadane's is conceptually simpler; you don't need to manage a trailing pointer unless you are asked to return the specific indices of the subarray.

Similar Problems

• 152. Maximum Product Subarray — Kadane's variant tracking both min and max to handle negative multiplications.
• 121. Best Time to Buy and Sell Stock — Can be solved identically if you map the array to daily price deltas.
• 918. Maximum Sum Circular Subarray — Kadane's extended to a wrap-around array.

Mind-Map Tags

#kadane #dynamic-programming #greedy #subarray-sum #optimal-substructure