Skip to main content

Pattern 1c: Subarray Optimization

Core Concept: Find optimal contiguous subarray ending at each position. Key distinction: dp[i] must include element at index i.

The Pattern​

THE MENTAL MODEL

Imagine scanning an array left-to-right:

  1. At each position i, you must include nums[i]
  2. Decision: Extend previous subarray OR start fresh from i
  3. Keep track of global maximum separately
  4. Formula: dp[i] = max(dp[i-1] + nums[i], nums[i])

This is Kadane's Algorithm - the foundation of subarray optimization.

Pattern Recognition​

WHEN YOU SEE THIS PATTERN

Keywords: "contiguous subarray", "maximum sum", "must include", "ending at position i"

Structure:

  • Must find optimal contiguous subarray
  • State definition: "best answer ending at position i"
  • Decision: extend vs. start fresh
  • Track global optimum separately from dp[i]

State: dp[i] = best answer for subarray ending at position i

Key Transition:

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

The Critical Distinction​

"UP TO i" vs "ENDING AT i"

This is Pattern 1c's defining characteristic:

Pattern 1a & 1b: dp[i] = best answer up to position i

  • May or may not include element at index i
  • Cumulative best so far

Pattern 1c: dp[i] = best answer ending at position i

  • MUST include element at index i
  • Local best at this position

Example (Maximum Subarray):

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

dp[4] (Pattern 1c) = best sum ENDING at index 4
     = [4, -1] = 3 (includes nums[4])

maxSum (global) = best sum UP TO index 4
        = [4] = 4 (may not include nums[4])

Problems in This Category​

Core Problems​

  1. Maximum Subarray (LC 53) - The canonical Kadane's Algorithm
  2. Maximum Product Subarray (LC 152) - Track both max and min
  3. Maximum Sum Circular Subarray (LC 918) - Circular array variant

Why Subarrays Need This Approach​

THE INSIGHT

Why not just use dp[i] = max(dp[i-1], nums[i])?

Because we need to know if the previous subarray is still worth extending.

If dp[i-1] is negative and nums[i] is positive, starting fresh is better!

Example:

nums = [-5, 3]
dp[0] = -5
dp[1] = ?

Option 1: dp[1] = dp[0] + nums[1] = -5 + 3 = -2
Option 2: dp[1] = nums[1] = 3 ✓ (start fresh)

We choose 3 because extending the negative sum makes things worse!

Template Code​

Standard Kadane's Algorithm​

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 previous subarray or start fresh
        dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);

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

    return maxSum;
}

Space-Optimized Kadane's​

public int maxSubArrayOptimized(int[] nums) {
    int currentSum = nums[0];  // dp[i]
    int maxSum = nums[0];      // global max

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

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

    return maxSum;
}

The Decision Logic​

// At each position i:
if (dp[i-1] + nums[i] > nums[i]) {
    // Previous subarray is worth extending
    dp[i] = dp[i-1] + nums[i];
} else {
    // Better to start fresh from current element
    dp[i] = nums[i];
}

// Simplified:
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);

Key Insights​

KADANE'S ALGORITHM INSIGHTS

Why this works:

  1. Local Decision: At each position, make locally optimal choice
  2. Extend or Reset: If previous sum helps, extend; otherwise reset
  3. Global Tracking: Keep separate variable for best answer seen so far

The Power:

  • ✅ O(n) time - single pass through array
  • ✅ O(1) space - only need two variables
  • ✅ Handles all negative arrays correctly
  • ✅ Works for all integer values

Edge Cases:

nums = [-2, -1]  → maxSum = -1 (best single element)
nums = [1]       → maxSum = 1
nums = [5, -3, 5] → maxSum = 7 (entire array)

Variations​

Maximum Product Subarray​

Twist: Track BOTH maximum and minimum (negative × negative = positive!)

public int maxProduct(int[] nums) {
    int maxDP = nums[0];
    int minDP = nums[0];
    int result = nums[0];

    for (int i = 1; i < nums.length; i++) {
        // Negative number can flip min to max
        int tempMax = maxDP;
        maxDP = Math.max(nums[i], Math.max(maxDP * nums[i], minDP * nums[i]));
        minDP = Math.min(nums[i], Math.min(tempMax * nums[i], minDP * nums[i]));

        result = Math.max(result, maxDP);
    }

    return result;
}

Common Mistakes​

PITFALLS

Mistake 1: Forgetting to track global max​

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

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

Mistake 2: Not starting fresh when needed​

// WRONG
dp[i] = dp[i-1] + nums[i];  // ❌ Always extending, even when harmful

// CORRECT
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);  // ✓ Start fresh if better

Mistake 3: Confusing with Pattern 1b​

// Pattern 1b (House Robber):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])  // Choose between i-1 and i-2

// Pattern 1c (Kadane):
dp[i] = max(dp[i-1] + nums[i], nums[i])  // Extend i-1 or start fresh

Key Differences from Other Patterns​

DON'T CONFUSE WITH

vs. Pattern 1a (Simple Accumulation):

  • 1a: dp[i] = count/ways up to i
  • 1c: dp[i] = best sum ending at i

vs. Pattern 1b (Selection with Skip):

  • 1b: dp[i] = best with skip constraint up to i
  • 1c: dp[i] = best contiguous subarray ending at i

Key: Pattern 1c requires contiguity (no gaps allowed in subarray)

Learning Path​

MASTER THIS PATTERN

Phase 1: Foundation

  1. Maximum Subarray (LC 53) - Master Kadane's Algorithm
  2. Best Time to Buy and Sell Stock (LC 121) - Kadane's variation

Phase 2: Variations 3. Maximum Product Subarray (LC 152) - Track both max and min 4. Maximum Sum Circular Subarray (LC 918) - Handle circular arrays

Key Insight: Once you understand "ending at i" vs "up to i", you'll know when to use Kadane's!

Final Thoughts​

THIS PATTERN IS ELEGANT

Kadane's Algorithm is a masterpiece:

  • Solves a complex problem in O(n) time, O(1) space
  • Clean, elegant logic
  • Handles all edge cases naturally
  • Foundation for many subarray optimization problems

Remember the core idea:

At each position, decide: Extend or start fresh?

Next Steps​

After mastering Pattern 1c:

  • ✅ You'll recognize "contiguous subarray" → Kadane's pattern
  • ✅ You'll understand "ending at i" state definition
  • ✅ You'll see Kadane's variations in many problems

Master these 3 subpatterns (1a, 1b, 1c) and you've mastered Pattern 1!