53. Maximum Subarray

At a Glance

• Topic: arrays-hashing
• Pattern: Kadane (DP-1D)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, LinkedIn
• Frequency: Very High
• LeetCode: 53

Problem (one-liner)

Given integer array numbers, find a contiguous subarray (at least one element) whose sum is maximum, and return that sum.

Recognition Cues

• "Maximum subarray sum", "contiguous"
• Negative numbers allowed — reset subarray when running sum drops below zero (classic Kadane)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — all O(n²) subarrays — O(n³) if recomputing sum each time naïvely.
• Better — prefix sums + min prefix — O(n) time.
• Optimal — Kadane: bestEndingHere = max(num, bestEndingHere + num) — O(n) time / O(1) space.

Optimal Solution

Go

package main

func maxSubArray(numbers []int) int {
	bestOverall := numbers[0]
	bestEndingHere := numbers[0]
	for index := 1; index < len(numbers); index++ {
		value := numbers[index]
		if bestEndingHere+value < value {
			bestEndingHere = value
		} else {
			bestEndingHere += value
		}
		if bestEndingHere > bestOverall {
			bestOverall = bestEndingHere
		}
	}
	return bestOverall
}

JavaScript

function maxSubArray(numbers) {
	let bestOverall = numbers[0];
	let bestEndingHere = numbers[0];
	for (let index = 1; index < numbers.length; index++) {
		const value = numbers[index];
		bestEndingHere = Math.max(value, bestEndingHere + value);
		bestOverall = Math.max(bestOverall, bestEndingHere);
	}
	return bestOverall;
}

Walkthrough

numbers = [-2,1,-3,4,-1,2,1,-5,4]

Continuing yields peak 6 for [4,-1,2,1].

Edge Cases

• All negative — answer is max single element (largest less negative).
• Single element array — that value.

Pitfalls

• Greedy "drop negatives" without Kadane — fails when all negative.
• Empty array — usually not given.

Similar Problems

• 152. Maximum Product Subarray — track min and max products.
• 121. Best Time to Buy and Sell Stock — related scan / profit as delta sum.
• 238. Product of Array Except Self — prefix/suffix accumulation.

Variants

• Return indices of optimal subarray.
• Circular array maximum sum — two-pass Kadane + total sum trick.

Mind-Map Tags

#kadane #dp #subarray #prefix-state #greedy-choice