Maximum Subarray

• Difficulty: Medium
• Topics: Array, Divide and Conquer, Dynamic Programming
• Link: https://leetcode.com/problems/maximum-subarray/

Problem Description

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

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 <= 105
• -104 <= nums[i] <= 104

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.

Solution

1. Problem Deconstruction

Technical Restatement
Given an integer array nums of length n ≥ 1, find the contiguous subarray (sequence of elements nums[i], nums[i+1], …, nums[j] where 0 ≤ i ≤ j < n) with the maximum possible sum. Return this sum.

Beginner Explanation
Imagine you have a list of numbers, some positive and some negative. Your task is to find a continuous block of numbers in this list that adds up to the largest possible total. You must select at least one number.

Mathematical Formulation
Let S(i, j) = Σ_{k=i}^j nums[k]. Find:

$$\max_{0 \leq i \leq j < n} S(i, j)$$

Constraint Analysis

1. 1 <= nums.length <= 1e5:
   • Eliminates O(n²) brute-force approaches (1e10 operations impractical).
   • Requires O(n) or O(n log n) solutions.
2. -1e4 <= nums[i] <= 1e4:
   • Negative values require handling subarrays that “reset” when cumulative sums turn negative.
   • Edge case: All elements negative → solution is the least negative element.
3. At least one element:
   • No need to handle empty arrays.

---

2. Intuition Scaffolding

Analogies

1. Real-World: Tracking daily profits/losses. Find the longest consecutive period with maximum net gain.
2. Gaming: Collecting power-ups in a platformer game where some boost points (+x) and others drain (-y). Find the best consecutive segment for a high score.
3. Mathematical: Maximizing the integral of a piecewise function over a continuous interval.

Common Pitfalls

1. Global Min/Max Fallacy: Assuming the maximum subarray starts at the global minimum or ends at the global maximum.
2. Premature Reset: Resetting the current sum to 0 instead of nums[i] when cumulative sums dip below zero.
3. Single-Pass Greedy Errors: Incorrectly assuming the first positive number starts the optimal subarray.
4. Divide-and-Conquer Overlook: Missing cross-subarray sums when splitting the problem.
5. Negative Handling: Failing to account for arrays with all negative values.

---

3. Approach Encyclopedia

Brute Force (Rejected)

• Pseudocode:

  max_sum = -inf  
  for i in 0 to n-1:  
      current_sum = 0  
      for j in i to n-1:  
          current_sum += nums[j]  
          max_sum = max(max_sum, current_sum)  
  return max_sum  
  

• Complexity: O(n²) time, O(1) space → Fails for n=1e5.

Kadane’s Algorithm (Optimal)

• Intuition: Track maximum sum ending at each position.
• Pseudocode:

  max_current = max_global = nums[0]  
  for num in nums[1:]:  
      max_current = max(num, max_current + num)  
      max_global = max(max_global, max_current)  
  return max_global  
  

• Complexity:
  • Time: O(n) → Each element processed once.
  • Space: O(1) → Two variables.
• Visualization:

  nums: [-2, 1, -3, 4, -1, 2, 1, -5, 4]  
  max_current: [-2 → 1 → -2 → 4 → 3 → 5 → 6 → 1 → 5]  
  max_global:   [-2 → 1 → 1 → 4 → 4 → 5 → 6 → 6 → 6]  
  

Divide and Conquer (Follow-Up)

• Intuition: Recursively split array into halves; compute max in left, right, and cross-mid.
• Pseudocode:

  def maxSubArray(nums):  
      def helper(l, r):  
          if l == r:  
              return nums[l]  
          mid = (l + r) // 2  
          left = helper(l, mid)  
          right = helper(mid+1, r)  
          # Compute cross sum  
          left_sum = right_sum = -inf  
          curr = 0  
          for i in range(mid, l-1, -1):  
              curr += nums[i]  
              left_sum = max(left_sum, curr)  
          curr = 0  
          for i in range(mid+1, r+1):  
              curr += nums[i]  
              right_sum = max(right_sum, curr)  
          return max(left, right, left_sum + right_sum)  
      return helper(0, len(nums)-1)  
  

• Complexity:
  • Time: O(n log n) → Recurrence T(n) = 2T(n/2) + O(n).
  • Space: O(log n) → Recursion depth.

---

4. Code Deep Dive

Optimal Solution (Kadane’s)

def maxSubArray(nums):  
    if not nums:  
        return 0  
    max_current = max_global = nums[0]  
    for num in nums[1:]:  
        max_current = max(num, max_current + num)  # Key decision: extend or restart  
        if max_current > max_global:  
            max_global = max_current  
    return max_global  

Line-by-Line Analysis

1. Initialization: max_current and max_global set to nums[0] to handle single-element cases.
2. Loop: Iterate from second element (nums[1]).
3. Decision Point: max(num, max_current + num) determines whether to start a new subarray at num or extend the previous subarray.
4. Global Update: Track the highest sum encountered.

Edge Case Handling

• All Negatives: Algorithm selects the least negative (e.g., [-3, -1, -2] → -1).
• Single Element: Directly returns nums[0].
• Mid-Array Reset: Example 1 restarts at 4 after cumulative sum 1 + (-3) = -2 < 4.

---

5. Complexity War Room

Hardware-Aware Analysis

• Kadane’s: 1e5 iterations → ~0.1ms on modern CPUs (1e6 ops/ms).
• Divide and Conquer: 1e5 log₂(1e5) ≈ 1.7e6 operations → ~1.7ms.

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(1)	8/10	❌
Kadane’s	O(n)	O(1)	9/10	✅
Divide & Conquer	O(n log n)	O(log n)	6/10	✅ (Follow-Up)

---

6. Pro Mode Extras

Variants

1. Maximum Subarray Sum with Non-Negativity Constraint: Trivial (sum all positives).
2. Maximum Subarray Product (LC 152): Adapt Kadane’s tracking min/max products.
3. Two Transactions (LC 123): Extend Kadane’s with forward/backward passes.

Interview Cheat Sheet

• First Mention: “This is a classic Kadane’s algorithm problem with O(n) time.”
• Edge Cases: Always test all-negative and single-element inputs.
• Follow-Up: “The divide-and-conquer approach is O(n log n), but Kadane’s is optimal for this problem.”