LeetCode · #53

Maximum Subarray Solution

Given an integer array, find the subarray with the largest sum and return its sum.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #53

🏗️

Pattern

Greedy / DP — Kadane's algorithm

Given integer array nums, find the contiguous subarray (containing at least one element) with the largest sum and return its sum.

Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 // Subarray [4,-1,2,1] has the largest sum 6.

Constraints

• 1 ≤ nums.length ≤ 10⁵ • -10⁴ ≤ nums[i] ≤ 10⁴

Section Two · Approach 1

Brute Force — O(n²)

Try every subarray start and end. Track running sum and global max.

Problem: O(n²) is too slow for n=10⁵. Kadane's insight: if the running sum drops below 0, reset — a negative prefix can only hurt future sums.

Java — O(n²)

 class Solution {
public int maxSubArray(int[] nums) {
int best = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                best = Math.max(best, sum);
            }
        }
return best;
    }
}

Python — O(n²)

 class Solution:
def maxSubArray(self, nums: list[int]) -> int:
        best = float('-inf')
for i in range(len(nums)):
            s = 0 for j in range(i, len(nums)):
                s += nums[j]
                best = max(best, s)
return best

Section Three · Approach 2

Kadane's Algorithm — O(n) time, O(1) space

Maintain a running sum cur. At each element: cur = max(nums[i], cur + nums[i]). If the previous sum is negative, start fresh. Track the global maximum.

💡 Mental model: You're carrying a bucket collecting water (positive numbers) and leaking water (negative numbers). At each step, you either keep carrying the bucket or dump it and start with a fresh bucket. The answer is the most water you ever had in the bucket. Kadane's says: if the bucket is lighter than what you'd get starting fresh (i.e., running sum < current element alone), dump and restart.

Algorithm

cur = nums[0], best = nums[0].
For i from 1 to n-1: cur = max(nums[i], cur + nums[i]). best = max(best, cur).
Return best.

🎯 When to recognize this pattern: "Maximum sum contiguous subarray." THE classic greedy/DP problem. Kadane's is the answer. Variants: LC 152 (Maximum Product Subarray — track min and max), LC 918 (Max Circular Subarray — handle wrap-around).

Section Four · Trace

Visual Walkthrough

Trace for nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4].

Maximum Subarray — Kadane's

Section Five · Implementation

Code — Java & Python

Java — Kadane's

 class Solution {
public int maxSubArray(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]); // extend or restart
best = Math.max(best, cur);
        }
return best;
    }
}

Python — Kadane's

 class Solution:
def maxSubArray(self, nums: list[int]) -> int:
        cur = best = nums[0]
for n in nums[1:]:
            cur = max(n, cur + n)
            best = max(best, cur)
return best

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force	O(n²)	O(1)	All subarrays
Divide & conquer	O(n log n)	O(log n)	Split + merge cross-sum
Kadane's ← optimal	O(n)	O(1)	Single pass, two variables

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All negative	`[-3,-2,-1]`	Answer is -1 (least negative). Kadane handles: never resets to 0.
Single element	`[5]`	Answer is 5.
All positive	`[1,2,3]`	Entire array is the answer. sum=6.
Zero in middle	`[1,0,-1]`	Best is [1,0]=1 or [1]=1.

⚠ Common Mistake: Initializing cur = 0 and best = 0. If all elements are negative, this returns 0 — which isn't a valid subarray sum (the problem requires at least one element). Always initialize with nums[0].

← Back to Greedy problems

LearningTree

LC 53 · Maximum Subarray — Solution & Explanation | DSA Guide