📊 Maximum Subarray (Kadane's Algorithm) - The Discovery Journey

The Problem (Quick Glance)

LC 53: Maximum Subarray

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

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

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

Initial Observations:

• This is a contiguous subarray problem - no gaps allowed
• Need to find maximum sum among all possible subarrays
• This is Pattern 1c: Subarray Optimization
• Classic application of Kadane's Algorithm

---

1. The Critical Distinction: "Ending At" vs "Up To"

THE KEY INSIGHT

Why Pattern 1c is different:

Most DP problems use:

• dp[i] = best answer up to position i

But subarray problems need:

• dp[i] = best answer ending at position i

Why?

Because we need to track whether the previous subarray is still worth extending!

Example: [-5, 3]

If dp[i] = "up to i":
  We'd get dp[1] = 3 (correct answer)
  But we wouldn't know: did we include -5 or not?

If dp[i] = "ending at i":
  dp[0] = -5 (best ending at index 0)
  dp[1] = max(-5 + 3, 3) = 3 (start fresh!)

This "ending at" state tells us whether to extend or restart!

---

2. The Kadane's Algorithm Intuition

COMING SOON

This section will explore:

• At each position: extend previous subarray OR start fresh
• Why we need to track current sum separately from max sum
• The elegant O(n) solution
• Why this is called "Kadane's Algorithm"

The Core Decision:

At each position i:
  currentSum = max(nums[i], currentSum + nums[i])
              ↑              ↑
         start fresh    extend previous

  maxSum = max(maxSum, currentSum)

---

3. Solution Evolution

COMING SOON

We'll build through these approaches:

Approach 1: Brute Force (Check All Subarrays)

// Try all possible subarrays
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // Calculate sum of subarray [i...j]
        int sum = 0;
        for (int k = i; k <= j; k++) {
            sum += nums[k];
        }
        maxSum = Math.max(maxSum, sum);
    }
}

• Time: O(n³) - Too slow!
• Space: O(1)

Approach 2: Optimized Brute Force

• Compute sum while expanding j
• Time: O(n²), Space: O(1)

Approach 3: Kadane's Algorithm (DP)

int currentSum = nums[0];
int maxSum = nums[0];

for (int i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
}

• Time: O(n), Space: O(1) - Optimal! ✓

---

4. The Kadane's Algorithm Formula

UNDERSTANDING THE FORMULA

dp[i] = Math.max(
    nums[i],           // Start fresh from current element
    dp[i-1] + nums[i]  // Extend previous subarray
)

When to start fresh?

• When dp[i-1] is negative and nums[i] is positive
• When extending would make the sum smaller

When to extend?

• When dp[i-1] + nums[i] > nums[i]
• When the previous sum is positive (helps us)

Tracking global maximum:

maxSum = Math.max(maxSum, dp[i])

We need this because dp[i] is the best ending at i, not the overall best!

---

5. Complete Implementation

// Kadane's Algorithm - O(n) time, O(1) space
public int maxSubArray(int[] nums) {
    int currentSum = nums[0];  // Best sum ending at current position
    int maxSum = nums[0];      // Global maximum

    for (int i = 1; i < nums.length; i++) {
        // Extend previous subarray or start fresh
        currentSum = Math.max(nums[i], currentSum + nums[i]);

        // Update global maximum
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

Alternative with explicit DP array:

public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int maxSum = dp[0];

    for (int i = 1; i < nums.length; i++) {
        // Either extend or start fresh
        dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);

        // Track global max
        maxSum = Math.max(maxSum, dp[i]);
    }

    return maxSum;
}

---

6. Execution Trace Example

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

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

i=0: currentSum = -2, maxSum = -2

i=1: currentSum = max(1, -2+1) = max(1, -1) = 1
     maxSum = max(-2, 1) = 1

i=2: currentSum = max(-3, 1+(-3)) = max(-3, -2) = -2
     maxSum = max(1, -2) = 1

i=3: currentSum = max(4, -2+4) = max(4, 2) = 4
     maxSum = max(1, 4) = 4

i=4: currentSum = max(-1, 4+(-1)) = max(-1, 3) = 3
     maxSum = max(4, 3) = 4

i=5: currentSum = max(2, 3+2) = max(2, 5) = 5
     maxSum = max(4, 5) = 5

i=6: currentSum = max(1, 5+1) = max(1, 6) = 6
     maxSum = max(5, 6) = 6 ✓

i=7: currentSum = max(-5, 6+(-5)) = max(-5, 1) = 1
     maxSum = max(6, 1) = 6

i=8: currentSum = max(4, 1+4) = max(4, 5) = 5
     maxSum = max(6, 5) = 6

Final Answer: 6
Subarray: [4, -1, 2, 1]

---

7. Why This Algorithm is Elegant

KADANE'S ALGORITHM BRILLIANCE

Key Insights:

1. Local Decision, Global Tracking

   • At each position, make locally optimal choice
   • Keep separate variable for global maximum

2. Handles All Cases

   • All positive numbers: extends entire array
   • All negative numbers: picks least negative
   • Mixed: finds optimal subarray

3. O(n) Time, O(1) Space

   • Single pass through array
   • Only 2 variables needed

4. Intuitive Logic

   • At each step: "Should I continue or start over?"
   • Simple max comparison answers this

This is one of the most elegant algorithms in computer science!

---

8. Common Mistakes

PITFALLS

Mistake 1: Forgetting to track global max

// WRONG
dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
return dp[n-1];  // ❌ Only returns best ENDING at last position!

// CORRECT
maxSum = Math.max(maxSum, dp[i]);  // Track global max
return maxSum;  // ✓ Return overall best

Mistake 2: Using accumulation instead of max

// WRONG - This is Pattern 1a (accumulation)
dp[i] = dp[i-1] + nums[i];  // ❌ Always extends

// CORRECT - This is Pattern 1c (optimization)
dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);  // ✓ Choose

Mistake 3: Not starting fresh when needed

// Example: [-5, 3]

// If we always extend:
dp[1] = dp[0] + nums[1] = -5 + 3 = -2  // ❌ Wrong!

// Correct approach:
dp[1] = max(3, -5 + 3) = 3  // ✓ Start fresh

---

9. Variations and Extensions

COMING SOON

Related Problems:

• Maximum Product Subarray (LC 152) - Track both max and min
• Maximum Sum Circular Subarray (LC 918) - Handle circular arrays
• Best Time to Buy and Sell Stock (LC 121) - Kadane's variation

Advanced Topics:

• Divide and Conquer approach
• What if we need to return the actual subarray?
• Handling empty subarrays

---

Coming Soon

MORE CONTENT COMING

We'll add:

• Detailed brute force approach analysis
• Why brute force is too slow
• Step-by-step evolution to Kadane's
• Divide and conquer alternative
• How to return the actual subarray
• Complete edge case analysis
• Variations and related problems

---

Key Takeaways

REMEMBER

1. ✅ Kadane's Algorithm is Pattern 1c: Subarray Optimization
2. ✅ Key: dp[i] = best sum ending at position i (not "up to")
3. ✅ Decision: extend previous subarray OR start fresh
4. ✅ Formula: currentSum = max(nums[i], currentSum + nums[i])
5. ✅ Must track global maximum separately
6. ✅ O(n) time, O(1) space - optimal solution
7. ✅ One of the most elegant algorithms in CS

This is a fundamental algorithm - understand it deeply!

---

Quick Solution Reference

// Kadane's Algorithm - Optimal Solution
public int maxSubArray(int[] nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

// Time: O(n), Space: O(1)