Kadane's Algorithm

This article covers the intuition, workflow, dry run, C++ implementation, complexity, and interview usage for Kadane's Algorithm.

1. Intuition

Kadane answers a beautiful question:

Should I extend the current subarray, or start fresh here?

If the running sum is hurting you, drop it. If it helps, keep it.

It exists because checking all subarrays is O(n^2), but the best subarray ending at each position can be updated in O(1).

2. How It Works

1. Track the best subarray ending at the current index
2. Either extend the old subarray or restart from the current value
3. Track the global maximum

3. Pattern Recognition

Think Kadane when you see:

• maximum subarray sum
• best contiguous score
• gain-loss streak
• transform problem into positive and negative contributions

4. Dry Run Example

Input:

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

Step-by-step execution:

• Start with -2, best = -2
• At 1, restart because 1 > -2 + 1
• At 4, restart again
• Extend through -1, 2, 1 to get 6

Final Output:

maximum subarray sum = 6

5. Code (C++)

int maxSubArray(const vector<int>& nums) {
  int current = nums[0];
  int best = nums[0];

  for (int i = 1; i < static_cast<int>(nums.size()); i++) {
    current = max(nums[i], current + nums[i]);
    best = max(best, current);
  }

  return best;
}

6. Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

7. When to Use

• maximum contiguous sum
• maximum difference after converting values
• stock-style transformed arrays

8. Common Mistakes

• initializing with 0 and failing all-negative arrays
• forgetting that this is for contiguous subarrays
• not storing the global answer separately

9. Variations / Extensions

• minimum subarray
• circular subarray sum
• 2D Kadane for maximum submatrix sum

10. LeetCode Practice Problems

Easy

• https://magicsheet.dev/questions/maximum-subarray/ - the classic

Medium

• https://magicsheet.dev/questions/maximum-sum-circular-subarray/

Hard

• https://magicsheet.dev/questions/maximum-sum-of-3-non-overlapping-subarrays/

11. Key Takeaways

• Kadane is a local decision with a global effect
• The question is always extend or restart
• Handle all-negative arrays carefully

Back: Arrays and Binary Search