Maximum Subarray

Mediumarraydynamic-programminggreedy
Category: Greedy
Companies that ask this question:
AmazonMicrosoftLinkedInBloombergApple
LeetCode →NeetCode →

Approach

Maximum Subarray (Kadane's Algorithm)

Problem Statement

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.

Approach: Kadane's Algorithm

Kadane's algorithm is an elegant greedy/dynamic programming solution.

Key Insight

At each position, we decide: should we extend the current subarray or start fresh?

  • If currentSum + nums[i] > nums[i], extend the subarray
  • Otherwise, start a new subarray from nums[i]

Algorithm

  1. Initialize: currentSum = 0, maxSum = -infinity
  2. For each element:
    • Add element to currentSum
    • Update maxSum = max(maxSum, currentSum)
    • If currentSum < 0, reset to 0 (start fresh)
  3. Return: maxSum

Time Complexity

  • Time: O(n) - single pass through array
  • Space: O(1) - only two variables

Example Walkthrough

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

i=0: curr=-2, max=-2 → reset curr=0
i=1: curr=1, max=1
i=2: curr=-2, max=1 → reset curr=0
i=3: curr=4, max=4
i=4: curr=3, max=4
i=5: curr=5, max=5
i=6: curr=6, max=6  ← Best subarray [4,-1,2,1]
i=7: curr=1, max=6
i=8: curr=5, max=6

Result: 6

Why It Works

The algorithm maintains the maximum sum ending at the current position. By resetting when currentSum < 0, we ensure we're always tracking the best possible subarray ending at or before the current index.

Key Insights

  1. Local decision: extend vs start fresh
  2. Track both current and maximum sums
  3. Negative current sum means starting fresh is better
  4. Works even with all negative numbers
  5. Can be modified to track subarray indices

Solution

java
1/**
2 * Maximum Subarray - Kadane's Algorithm
3 * Time: O(n), Space: O(1)
4 */
5
6class Solution {
7    public int maxSubArray(int[] nums) {
8        int maxSum = Integer.MIN_VALUE;
9        int currentSum = 0;
10        
11        for (int num : nums) {
12            currentSum += num;
13            maxSum = Math.max(maxSum, currentSum);
14            
15            if (currentSum < 0) {
16                currentSum = 0;
17            }
18        }
19        
20        return maxSum;
21    }
22}
23
24// Alternative
25class Solution2 {
26    public int maxSubArray(int[] nums) {
27        int maxSum = nums[0];
28        int currentSum = nums[0];
29        
30        for (int i = 1; i < nums.length; i++) {
31            currentSum = Math.max(nums[i], currentSum + nums[i]);
32            maxSum = Math.max(maxSum, currentSum);
33        }
34        
35        return maxSum;
36    }
37}
38
Loading visualizer...