289. Maximum Subarray

🔗 LeetCode Problem: 53. Maximum Subarray
📊 Difficulty: Medium
🏷️ Topics: Array, Dynamic Programming, Divide and Conquer, Kadane's Algorithm

Problem Statement

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

Follow-up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

🌳 Visual Understanding - The Maximum Subarray Problem

The Problem We're Solving:

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

A subarray = continuous elements

Examples of subarrays:
  [−2]
  [−2, 1]
  [−2, 1, −3]
  [1]
  [1, −3]
  [4, −1, 2, 1]  ← This one has sum = 6 (maximum!)
  [−5, 4]
  ...

Question: Which contiguous subarray has the MAXIMUM sum?

Understanding Subarrays:

For array [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

All possible subarrays (there are n*(n+1)/2 of them):

Length 1:
  [-2] → sum = -2
  [1] → sum = 1
  [-3] → sum = -3
  [4] → sum = 4
  [-1] → sum = -1
  [2] → sum = 2
  [1] → sum = 1
  [-5] → sum = -5
  [4] → sum = 4

Length 2:
  [-2, 1] → sum = -1
  [1, -3] → sum = -2
  [-3, 4] → sum = 1
  [4, -1] → sum = 3
  [-1, 2] → sum = 1
  [2, 1] → sum = 3
  [1, -5] → sum = -4
  [-5, 4] → sum = -1

Length 3:
  [-2, 1, -3] → sum = -4
  [1, -3, 4] → sum = 2
  [-3, 4, -1] → sum = 0
  [4, -1, 2] → sum = 5
  [-1, 2, 1] → sum = 2
  [2, 1, -5] → sum = -2
  [1, -5, 4] → sum = 0

Length 4:
  [-2, 1, -3, 4] → sum = 0
  [1, -3, 4, -1] → sum = 1
  [-3, 4, -1, 2] → sum = 2
  [4, -1, 2, 1] → sum = 6 ✓ MAXIMUM!
  ...

Maximum sum = 6 from subarray [4, -1, 2, 1]

Key Observations:

1. Must be CONTIGUOUS
   [4, 2, 1] is NOT valid if 2 is not next to 4

2. At least ONE element
   Empty subarray is not allowed

3. Can be single element
   If all negative, answer is the least negative number
   Example: [-3, -1, -5] → answer is -1

4. Can be entire array
   If all positive: [1, 2, 3] → answer is 6 (sum of all)

🧠 The AHA Moment - Why Dynamic Programming?

The Brute Force Observation:

To find maximum sum:
  Check ALL possible subarrays
  Compute sum of each
  Return maximum

But there are n*(n+1)/2 subarrays!
For n=9: 9*10/2 = 45 subarrays
For n=1000: 1000*1001/2 = 500,500 subarrays!

This is O(n²) or O(n³) depending on implementation! 😰

The Key Insight - Optimal Substructure:

Think about this:

If we know the maximum subarray ending at position i,
can we use it to find maximum subarray ending at position i+1?

Example: nums = [-2, 1, -3, 4]

At index 0: Best ending here = -2
At index 1: Best ending here = max(1, -2+1) = 1
At index 2: Best ending here = max(-3, 1+(-3)) = -2
At index 3: Best ending here = max(4, -2+4) = 4

Pattern: At each position, we DECIDE:
  "Should I extend previous subarray or START NEW?"

This is OPTIMAL SUBSTRUCTURE!
Perfect for DP! 🎯

Why This Works:

At each position i, we have TWO choices:

Choice 1: Include nums[i] in previous subarray
  Sum = (max sum ending at i-1) + nums[i]

Choice 2: Start fresh from nums[i]
  Sum = nums[i]

We pick whichever is larger!

This DECISION at each step leads to global optimum!
This is Kadane's Algorithm! ✨

🔴 Approach 1: Brute Force

📐 Function Definition

Function Signature:

int maxSubArray(int[] nums)

What it does: - Try ALL possible subarrays - Calculate sum of each - Return the maximum sum found

Approach: - Two nested loops for start and end indices - Third loop to calculate sum (or calculate on the fly) - Track maximum sum seen

💡 Intuition

"Check every possible subarray exhaustively"

For each starting index i:
  For each ending index j (where j >= i):
    Calculate sum from i to j
    Update maximum if this sum is larger

Straightforward but SLOW!

📝 Implementation - Version 1 (O(n³))

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;

        // Try all starting positions
        for (int start = 0; start < n; start++) {

            // Try all ending positions from start
            for (int end = start; end < n; end++) {

                // Calculate sum from start to end
                int currentSum = 0;
                for (int k = start; k <= end; k++) {
                    currentSum += nums[k];
                }

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

        return maxSum;
    }
}

📝 Implementation - Version 2 (O(n²) - Optimized)

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;

        // Try all starting positions
        for (int start = 0; start < n; start++) {
            int currentSum = 0;

            // Try all ending positions from start
            for (int end = start; end < n; end++) {
                // Add current element to running sum
                currentSum += nums[end];

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

        return maxSum;
    }
}

🔍 Dry Run: nums = [-2, 1, -3, 4, -1]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Using O(n²) optimized version
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

maxSum = -∞

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
START = 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

currentSum = 0

end=0: [-2]
  currentSum = 0 + (-2) = -2
  maxSum = max(-∞, -2) = -2

end=1: [-2, 1]
  currentSum = -2 + 1 = -1
  maxSum = max(-2, -1) = -1

end=2: [-2, 1, -3]
  currentSum = -1 + (-3) = -4
  maxSum = max(-1, -4) = -1

end=3: [-2, 1, -3, 4]
  currentSum = -4 + 4 = 0
  maxSum = max(-1, 0) = 0

end=4: [-2, 1, -3, 4, -1]
  currentSum = 0 + (-1) = -1
  maxSum = max(0, -1) = 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
START = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

currentSum = 0

end=1: [1]
  currentSum = 0 + 1 = 1
  maxSum = max(0, 1) = 1

end=2: [1, -3]
  currentSum = 1 + (-3) = -2
  maxSum = max(1, -2) = 1

end=3: [1, -3, 4]
  currentSum = -2 + 4 = 2
  maxSum = max(1, 2) = 2

end=4: [1, -3, 4, -1]
  currentSum = 2 + (-1) = 1
  maxSum = max(2, 1) = 2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
START = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

currentSum = 0

end=2: [-3]
  currentSum = 0 + (-3) = -3
  maxSum = max(2, -3) = 2

end=3: [-3, 4]
  currentSum = -3 + 4 = 1
  maxSum = max(2, 1) = 2

end=4: [-3, 4, -1]
  currentSum = 1 + (-1) = 0
  maxSum = max(2, 0) = 2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
START = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

currentSum = 0

end=3: [4]
  currentSum = 0 + 4 = 4
  maxSum = max(2, 4) = 4 ✓

end=4: [4, -1]
  currentSum = 4 + (-1) = 3
  maxSum = max(4, 3) = 4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
START = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

currentSum = 0

end=4: [-1]
  currentSum = 0 + (-1) = -1
  maxSum = max(4, -1) = 4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: maxSum = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Best subarray: [4]

📊 Complexity Analysis

Time Complexity: - Version 1 (3 loops): O(n³) - Version 2 (2 loops): O(n²)

Space Complexity: O(1)

No extra space except variables

Why This is Slow:

For n = 10,000:
  O(n²) = 100,000,000 operations
  Too slow for large inputs! ⚠️

Need better approach!

🟡 Approach 2: Dynamic Programming (Kadane's Algorithm)

📐 Function Definition

DP Definition:

int maxSubArray(int[] nums)

What we track:

At each position i:
  maxEndingHere = maximum sum of subarray ENDING at position i

Global answer:
  Maximum of all maxEndingHere values

Key Decision at Each Position:

maxEndingHere[i] = max(
  nums[i],                    // Start fresh from here
  maxEndingHere[i-1] + nums[i] // Extend previous subarray
)

💡 Intuition - The Core Insight

Think of walking through the array:

At each position, you ask:
  "Should I ADD this element to my current running sum?"
  "OR should I START FRESH from this element?"

Decision rule:
  If current running sum is NEGATIVE:
    → It's dragging us down!
    → Better to start fresh from current element

  If current running sum is POSITIVE:
    → It's helping us!
    → Add current element to it

This simple decision gives optimal answer! 🎯

🎨 Visual Discovery

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

Let's walk through and make decisions:

Position 0: -2
  No previous subarray
  maxEndingHere = -2
  globalMax = -2

Position 1: 1
  Previous sum: -2 (negative!)
  Decision: Start fresh! 1 is better than -2+1=-1
  maxEndingHere = 1
  globalMax = max(-2, 1) = 1

Position 2: -3
  Previous sum: 1 (positive!)
  Decision: Extend! 1+(-3)=-2 is better than just -3
  maxEndingHere = -2
  globalMax = max(1, -2) = 1

Position 3: 4
  Previous sum: -2 (negative!)
  Decision: Start fresh! 4 is better than -2+4=2
  maxEndingHere = 4
  globalMax = max(1, 4) = 4

Position 4: -1
  Previous sum: 4 (positive!)
  Decision: Extend! 4+(-1)=3 is better than just -1
  maxEndingHere = 3
  globalMax = max(4, 3) = 4

Position 5: 2
  Previous sum: 3 (positive!)
  Decision: Extend! 3+2=5 is better than just 2
  maxEndingHere = 5
  globalMax = max(4, 5) = 5

Position 6: 1
  Previous sum: 5 (positive!)
  Decision: Extend! 5+1=6 is better than just 1
  maxEndingHere = 6
  globalMax = max(5, 6) = 6 ✓

Position 7: -5
  Previous sum: 6 (positive!)
  Decision: Extend! 6+(-5)=1 is better than just -5
  maxEndingHere = 1
  globalMax = max(6, 1) = 6

Position 8: 4
  Previous sum: 1 (positive!)
  Decision: Extend! 1+4=5 is better than just 4
  maxEndingHere = 5
  globalMax = max(6, 5) = 6

ANSWER: 6

The subarray: [4, -1, 2, 1] with sum = 6

📝 Implementation - Version 1 (With DP Array)

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;

        // dp[i] = maximum sum of subarray ending at index i
        int[] dp = new int[n];

        // Base case: first element
        dp[0] = nums[0];
        int maxSum = dp[0];

        // Fill dp array
        for (int i = 1; i < n; i++) {
            // Decision: extend previous or start fresh?
            dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);

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

        return maxSum;
    }
}

📝 Implementation - Version 2 (Space Optimized - Kadane's)

class Solution {
    public int maxSubArray(int[] nums) {
        int maxEndingHere = nums[0];  // Max sum ending at current position
        int maxSoFar = nums[0];        // Global maximum

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

            // Update global maximum
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }
}

📝 Implementation - Version 3 (Most Intuitive)

class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = 0;     // Running sum
        int maxSum = Integer.MIN_VALUE;

        for (int num : nums) {
            // If current sum is negative, start fresh
            if (currentSum < 0) {
                currentSum = 0;
            }

            // Add current element
            currentSum += num;

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

        return maxSum;
    }
}

🔍 Complete Dry Run: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Using Kadane's Algorithm (Version 2):

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

maxEndingHere = nums[0] = -2
maxSoFar = nums[0] = -2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 1, nums[1] = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Decision:
  Option 1: Start fresh from 1 → 1
  Option 2: Extend previous -2+1 → -1
  Choose: max(1, -1) = 1 ✓

maxEndingHere = 1
maxSoFar = max(-2, 1) = 1

Interpretation: "Best subarray ending at index 1 is [1] with sum 1"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 2, nums[2] = -3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Decision:
  Option 1: Start fresh from -3 → -3
  Option 2: Extend previous 1+(-3) → -2
  Choose: max(-3, -2) = -2 ✓

maxEndingHere = -2
maxSoFar = max(1, -2) = 1

Interpretation: "Best subarray ending at index 2 is [1,-3] with sum -2"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 3, nums[3] = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Decision:
  Option 1: Start fresh from 4 → 4
  Option 2: Extend previous -2+4 → 2
  Choose: max(4, 2) = 4 ✓

maxEndingHere = 4
maxSoFar = max(1, 4) = 4

Interpretation: "Best subarray ending at index 3 is [4] with sum 4"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 4, nums[4] = -1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Decision:
  Option 1: Start fresh from -1 → -1
  Option 2: Extend previous 4+(-1) → 3
  Choose: max(-1, 3) = 3 ✓

maxEndingHere = 3
maxSoFar = max(4, 3) = 4

Interpretation: "Best subarray ending at index 4 is [4,-1] with sum 3"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 5, nums[5] = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Decision:
  Option 1: Start fresh from 2 → 2
  Option 2: Extend previous 3+2 → 5
  Choose: max(2, 5) = 5 ✓

maxEndingHere = 5
maxSoFar = max(4, 5) = 5

Interpretation: "Best subarray ending at index 5 is [4,-1,2] with sum 5"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 6, nums[6] = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Decision:
  Option 1: Start fresh from 1 → 1
  Option 2: Extend previous 5+1 → 6
  Choose: max(1, 6) = 6 ✓

maxEndingHere = 6
maxSoFar = max(5, 6) = 6

Interpretation: "Best subarray ending at index 6 is [4,-1,2,1] with sum 6"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 7, nums[7] = -5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Decision:
  Option 1: Start fresh from -5 → -5
  Option 2: Extend previous 6+(-5) → 1
  Choose: max(-5, 1) = 1 ✓

maxEndingHere = 1
maxSoFar = max(6, 1) = 6

Interpretation: "Best subarray ending at index 7 is [4,-1,2,1,-5] with sum 1"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i = 8, nums[8] = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Decision:
  Option 1: Start fresh from 4 → 4
  Option 2: Extend previous 1+4 → 5
  Choose: max(4, 5) = 5 ✓

maxEndingHere = 5
maxSoFar = max(6, 5) = 6

Interpretation: "Best subarray ending at index 8 is [4,-1,2,1,-5,4] with sum 5"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

maxSoFar = 6

The maximum subarray: [4, -1, 2, 1] with sum = 6 ✓

📊 Complexity Analysis

Time Complexity: O(n)

Single pass through array
Each operation: O(1)
Total: O(n) ✓

OPTIMAL! Can't do better!

Space Complexity: - Version 1 (with DP array): O(n) - Version 2 & 3 (Kadane's): O(1) ✓

(Continuing in next part due to length limit...)

🔵 Approach 3: Divide and Conquer

📐 The Divide and Conquer Concept

Key Idea:

Divide array into two halves
Maximum subarray is EITHER:
  1. Entirely in left half
  2. Entirely in right half  
  3. Crosses the middle (spans both halves)

Find maximum of these three!

💡 Intuition - Breaking Down the Problem

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
           LEFT          MID      RIGHT

Split at middle:
  Left:  [-2, 1, -3, 4]
  Right: [-1, 2, 1, -5, 4]

Maximum subarray could be:
  Case 1: Completely in left → Find recursively
  Case 2: Completely in right → Find recursively
  Case 3: Crosses middle → Special calculation

The crossing case is KEY!

🎯 Understanding the Crossing Case

When subarray crosses middle:
  It MUST include elements from both sides of middle

Example:
  Left:  [..., a, b, c] | Right: [d, e, f, ...]
                   ↑ mid        ↑

Crossing subarray: [b, c, d, e]
  Part in left: [b, c] (must touch middle)
  Part in right: [d, e] (must touch middle)

How to find it:
  1. Find best subarray in left ending at middle
  2. Find best subarray in right starting from middle+1
  3. Combine them!

📝 Implementation

class Solution {
    public int maxSubArray(int[] nums) {
        return divideAndConquer(nums, 0, nums.length - 1);
    }

    private int divideAndConquer(int[] nums, int left, int right) {
        // Base case: single element
        if (left == right) {
            return nums[left];
        }

        // Divide: find middle
        int mid = left + (right - left) / 2;

        // Conquer: recursively find max in left and right halves
        int leftMax = divideAndConquer(nums, left, mid);
        int rightMax = divideAndConquer(nums, mid + 1, right);

        // Combine: find max crossing subarray
        int crossMax = findCrossingMax(nums, left, mid, right);

        // Return maximum of three
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    private int findCrossingMax(int[] nums, int left, int mid, int right) {
        // Find best subarray in left half ending at mid
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }

        // Find best subarray in right half starting at mid+1
        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }

        // Combine left and right
        return leftSum + rightSum;
    }
}

🔍 Detailed Dry Run

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LEVEL 1: divideAndConquer(0, 8)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
mid = 4

Split into:
  Left: [-2, 1, -3, 4] (indices 0-4)
  Right: [-1, 2, 1, -5, 4] (indices 5-8)

Need to find:
  leftMax = divideAndConquer(0, 4)
  rightMax = divideAndConquer(5, 8)
  crossMax = findCrossingMax(0, 4, 8)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LEVEL 2a: divideAndConquer(0, 4) - LEFT HALF
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Array: [-2, 1, -3, 4, -1]
mid = 2

Split into:
  Left: [-2, 1] (indices 0-2)
  Right: [-3, 4, -1] (indices 3-4)

This continues recursively...
Eventually returns: leftMax = 4 (from subarray [4])

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LEVEL 2b: divideAndConquer(5, 8) - RIGHT HALF
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Array: [2, 1, -5, 4]
This continues recursively...
Eventually returns: rightMax = 4 (from subarray [4])

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CROSSING CASE: findCrossingMax(0, 4, 8)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

mid = 4 (element = -1)

Find best ending at mid (going left from 4):
  i=4: sum = -1, leftSum = -1
  i=3: sum = -1+4 = 3, leftSum = 3
  i=2: sum = 3+(-3) = 0, leftSum = 3
  i=1: sum = 0+1 = 1, leftSum = 3
  i=0: sum = 1+(-2) = -1, leftSum = 3

  Best in left: leftSum = 3 (subarray [4, -1])

Find best starting at mid+1 (going right from 5):
  i=5: sum = 2, rightSum = 2
  i=6: sum = 2+1 = 3, rightSum = 3
  i=7: sum = 3+(-5) = -2, rightSum = 3
  i=8: sum = -2+4 = 2, rightSum = 3

  Best in right: rightSum = 3 (subarray [2, 1])

crossMax = leftSum + rightSum = 3 + 3 = 6 ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMBINE RESULTS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

leftMax = 4
rightMax = 4
crossMax = 6

Return max(4, 4, 6) = 6 ✓

The crossing subarray: [4, -1, 2, 1] with sum = 6

📊 Complexity Analysis

Time Complexity: O(n log n)

Recurrence: T(n) = 2T(n/2) + O(n)
  Two recursive calls on halves: 2T(n/2)
  Finding crossing max: O(n)

By Master Theorem: T(n) = O(n log n)

Slower than Kadane's O(n), but interesting approach!

Space Complexity: O(log n)

Recursion stack depth: O(log n)

📊 Approach Comparison

┌─────────────────┬──────────────┬──────────┬──────────────────┐
│ Approach        │ Time         │ Space    │ Key Idea         │
├─────────────────┼──────────────┼──────────┼──────────────────┤
│ Brute Force     │ O(n²) or O(n³)│ O(1)    │ Try all subarrays│
│ DP (Kadane's)   │ O(n)         │ O(1)     │ Local decision   │
│ Divide & Conquer│ O(n log n)   │ O(log n) │ Split & combine  │
└─────────────────┴──────────────┴──────────┴──────────────────┘

Kadane's Algorithm is the BEST! ✨

💡 Key Learnings - Kadane's Algorithm Deep Dive

The Core Principle

At each position, ONE simple decision:
  "Should I extend previous subarray or start fresh?"

Mathematical formulation:
  maxEndingHere = max(nums[i], maxEndingHere + nums[i])

In plain English:
  "Is current element alone better, or adding it to previous sum better?"

This local optimal decision leads to global optimal solution! 🎯

Why Kadane's Works - Intuitive Proof

Claim: Kadane's algorithm finds the maximum subarray sum

Proof (by contradiction):

Assume Kadane's doesn't find the optimal subarray.
Let the optimal subarray be [i, j] with sum S.

Case 1: Kadane's never considered including element i
  → But Kadane's checks every element!
  → Contradiction!

Case 2: Kadane's considered i but chose different subarray
  → At position i, Kadane's either:
    a) Starts fresh from i (if previous sum < 0)
    b) Extends from before (if previous sum ≥ 0)

  → Both choices are optimal at that point!
  → If starting fresh was better, doing so IS optimal
  → If extending was better, doing so IS optimal
  → Contradiction!

Therefore, Kadane's always finds the optimal solution! ✓

The Pattern - When Kadane's Applies

Kadane's works when problem has:
  1. Linear scan property (can process left to right)
  2. Local optimal decision (choice at each step)
  3. Optimal substructure (local optimal → global optimal)

Similar problems:
  - Maximum product subarray (with modification)
  - Best time to buy and sell stock
  - Maximum sum circular subarray

🎯 Pattern Recognition - Maximum Subarray Pattern

Template for Similar Problems

// Kadane's Algorithm Template
class Solution {
    public int maxSubArray(int[] nums) {
        int maxEndingHere = nums[0];
        int maxSoFar = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // KEY DECISION: Extend or start fresh?
            maxEndingHere = max(nums[i], maxEndingHere + nums[i]);

            // Track global maximum
            maxSoFar = max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }
}

1. Maximum Product Subarray (LC 152)

Similar to sum, but with multiplication
Need to track both max and min (negative numbers!)

2. Best Time to Buy and Sell Stock (LC 121)

Same pattern: track minimum so far, maximize profit

3. Maximum Sum Circular Subarray (LC 918)

Extension: subarray can wrap around
Two cases: normal max or total - min

⚠️ Common Mistakes

// Mistake 1: Not handling all negatives
int maxSum = 0;  // ❌ Wrong! If all negative, this returns 0
for (int num : nums) {
    currentSum += num;
    maxSum = max(maxSum, currentSum);
}

// ✓ CORRECT: Initialize with first element
int maxSum = nums[0];

// Mistake 2: Not resetting when sum goes negative
int sum = 0;
for (int num : nums) {
    sum += num;  // ❌ Keeps accumulating negatives
    maxSum = max(maxSum, sum);
}

// ✓ CORRECT: Reset when negative
if (sum < 0) sum = 0;

// Mistake 3: Forgetting the decision
int sum = 0;
for (int num : nums) {
    sum = num;  // ❌ Always starts fresh! Wrong!
}

// ✓ CORRECT: Make the decision
sum = max(num, sum + num);

🎓 Practice Exercises

Exercise 1: Trace Yourself

Trace Kadane's algorithm on: nums = [5, -3, 5]

Initial: maxEndingHere = 5, maxSoFar = 5

i=1 (nums[1]=-3):
  Decision: max(-3, 5+(-3)) = max(-3, 2) = ?
  maxEndingHere = ?
  maxSoFar = ?

i=2 (nums[2]=5):
  Decision: max(5, ?+5) = ?
  maxEndingHere = ?
  maxSoFar = ?

Answer: ?

(Solution: maxSoFar = 7, subarray [5, -3, 5])

Exercise 2: Edge Cases

What's the answer for these?

1. nums = [-1]
   Answer: ?

2. nums = [-2, -1]
   Answer: ?

3. nums = [1, 2, 3, 4, 5]
   Answer: ?

(Solutions: -1, -1, 15)

📝 Quick Revision Notes

🎯 Core Concept

Problem: Find contiguous subarray with maximum sum

Best Solution: Kadane's Algorithm - O(n) time, O(1) space

Key Decision at Each Element:

maxEndingHere = max(nums[i], maxEndingHere + nums[i])
               ↑              ↑
         Start fresh    Extend previous

Why It Works: Local optimal choices lead to global optimal solution

⚡ Quick Implementation

public class Solution {
  public int maxSubArray(int[] a) {
    // return naive(a);
    // return kadane(a);
    return kadaneSpaceOptimal(a);
  }

  private int kadaneSpaceOptimal(int[] a) {
    // Exactly same as kandane except that we space optimized DP array
    int n = a.length;
    int maxTillNow = a[0];
    int res = a[0];

    for (int i = 1; i < n; i++) {
      maxTillNow = Math.max(a[i], a[i] + maxTillNow);

      res = Math.max(maxTillNow, res);
    }

    return res;
  }

  private int kadane(int[] a) {
    int n = a.length;

    // step 1: dp[i] => max subarray sum ending at index i
    int[] dp = new int[n];
    dp[0] = a[0];

    // step 2: why res separately?
    // dp[i] has result of subarray that ends at index i
    // there may be a case where dp[i-1] > dp[i] when a[i] is -ve
    // Hence, track it separately
    int res = a[0];

    for (int i = 1; i < n; i++) {
      // step 3:
      // case 1: only +ve numbers => always a[i] + dp[i - 1]
      // case 2: mix of +ve and -ve numbers =>
      // example: max(1, 1+(-5)) => 1
      dp[i] = Math.max(a[i], a[i] + dp[i - 1]);

      // step 4: track global result
      res = Math.max(res, dp[i]);
    }

    return res;
  }

  private int naive(int[] a) {
    // generate all subarrays
    int n = a.length;
    int res = Integer.MIN_VALUE;

    for (int i = 0; i < n; i++) {
      int runningSum = 0;

      for (int j = i; j < n; j++) {
        runningSum += a[j];

        res = Math.max(res, runningSum);
      }
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.maxSubArray(new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 }) == 6);
    System.out.println(s.maxSubArray(new int[] { 1 }) == 1);
    System.out.println(s.maxSubArray(new int[] { 5, 4, -1, 7, 8 }) == 23);
  }
}

🔑 Key Points

✓ Must be CONTIGUOUS (no gaps allowed)
✓ At least ONE element required
✓ Can be single element (if all negative)
✓ Can be entire array (if all positive)
✓ Decision: extend vs start fresh
✓ Track TWO values: maxEndingHere + maxSoFar
✓ Time: O(n), Space: O(1)

🎪 Memory Aid

"At each step, ask: extend or restart?"
"Negative drags down → restart!"
"Positive helps → extend!"
"Track max ending here + max so far!" ✨

🎉 Congratulations!

You've mastered the Maximum Subarray problem!

What You Learned:

✅ Brute Force - Try all subarrays (O(n²))
✅ Kadane's Algorithm - Optimal DP solution (O(n))
✅ Divide and Conquer - Alternative approach (O(n log n))
✅ Local vs Global - How local decisions build global solution
✅ Pattern Recognition - Template for similar problems

The Beautiful Insight:

Complex Problem → Simple Solution

The magic of Kadane's:
  At each step: ONE simple decision
  Result: Global optimal solution

This is the power of Dynamic Programming:
  Break complex problem into simple decisions
  Combine simple solutions into complex answer

Kadane's Algorithm = Classic DP mastery! 🎯

Interview Mastery:

When asked about Maximum Subarray:

1. Start with brute force: "Try all subarrays - O(n²)"

2. Optimize with Kadane's: "At each position, decide:
   extend previous or start fresh?"

3. Explain decision: "If previous sum is negative,
   it hurts us, so start fresh. Otherwise extend."

4. Code it up: Clean O(n) solution

5. Mention divide & conquer: "There's also O(n log n)
   approach using divide and conquer..."

Shows complete understanding! 💯

You've now mastered one of the most elegant DP algorithms! 🚀✨🎯

289. Maximum Subarray

Problem Statement

🌳 Visual Understanding - The Maximum Subarray Problem

The Problem We're Solving:

Understanding Subarrays:

Key Observations:

🧠 The AHA Moment - Why Dynamic Programming?

The Brute Force Observation:

The Key Insight - Optimal Substructure:

Why This Works:

🔴 Approach 1: Brute Force

📐 Function Definition

💡 Intuition

📝 Implementation - Version 1 (O(n³))

📝 Implementation - Version 2 (O(n²) - Optimized)

🔍 Dry Run: nums = [-2, 1, -3, 4, -1]

📊 Complexity Analysis

🟡 Approach 2: Dynamic Programming (Kadane's Algorithm)

📐 Function Definition

💡 Intuition - The Core Insight

🎨 Visual Discovery

📝 Implementation - Version 1 (With DP Array)

📝 Implementation - Version 2 (Space Optimized - Kadane's)

📝 Implementation - Version 3 (Most Intuitive)

🔍 Complete Dry Run: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

📊 Complexity Analysis

🔵 Approach 3: Divide and Conquer

📐 The Divide and Conquer Concept

💡 Intuition - Breaking Down the Problem

🎯 Understanding the Crossing Case

📝 Implementation

🔍 Detailed Dry Run

📊 Complexity Analysis

📊 Approach Comparison

💡 Key Learnings - Kadane's Algorithm Deep Dive

The Core Principle

Why Kadane's Works - Intuitive Proof

The Pattern - When Kadane's Applies

🎯 Pattern Recognition - Maximum Subarray Pattern

Template for Similar Problems

Related Problems

⚠️ Common Mistakes

🎓 Practice Exercises

Exercise 1: Trace Yourself

Exercise 2: Edge Cases

📝 Quick Revision Notes

🎯 Core Concept

⚡ Quick Implementation

🔑 Key Points

🎪 Memory Aid

🎉 Congratulations!

What You Learned:

The Beautiful Insight:

Interview Mastery: