🔥 Introduction

Imagine you’re tracking your daily mood for a month. Some days are amazing (+ve), others are tough (-ve). One day, someone asks:

"When were you the happiest — not in number of days, but in total mood points?"

That’s what Kadane’s Algorithm helps you solve — not in therapy, but in arrays.

🤔 The Problem

Given an array of integers (both positive and negative), find the maximum sum of any contiguous subarray.

🧪 Example:

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6  → Subarray: [4, -1, 2, 1]

🛠️ Brute Force? No Thanks!

We could check all possible subarrays (nested loops), but that would take O(n²) or even O(n³) time — not ideal for large datasets.

💡 Kadane’s Insight

At any index i, you have two options:

  1. Start a new subarray from nums[i]
  2. Extend the previous subarray by adding nums[i]

Kadane’s Algorithm says:
Choose the option that gives a higher sum.

🧾 Algorithm Steps

We maintain two variables:

  • currentSum: max sum ending at current index
  • maxSoFar: max sum found so far

🧠 Formula:

currentSum = max(nums[i], currentSum + nums[i])
maxSoFar = max(maxSoFar, currentSum)

🔢 TypeScript Implementation

function maxSubArray(nums: number[]): number {
    let currentSum = nums[0];
    let maxSoFar = nums[0];

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

    return maxSoFar;
}

🔍 Dry Run: Let’s Understand It Line by Line

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

i arr[i] currentSum maxSoFar
0 -2 -2 -2
1 1 max(1, -2+1) = 1 1
2 -3 max(-3, 1-3) = -2 1
3 4 max(4, -2+4) = 4 4
4 -1 max(-1, 4-1) = 3 4
5 2 max(2, 3+2) = 5 5
6 1 max(1, 5+1) = 6 6
7 -5 max(-5, 6-5) = 1 6
8 4 max(4, 1+4) = 5 6

🎯 Final Answer: 6

🔄 Variations of Kadane’s Algorithm

1. Maximum Product Subarray

Track both max and min products at each step due to negative numbers flipping signs.

2. Maximum Circular Subarray

Use Kadane twice:
max(sum of array - min subarray sum, kadane on normal array)

3. Maximum Sum Rectangle in 2D Matrix

Apply Kadane on row-wise collapsed 1D arrays between two columns.

4. Best Time to Buy and Sell Stock

Convert to difference array and apply Kadane to find max profit window.

📘 Teaching Philosophy

Kadane’s Algorithm teaches more than just coding:

  • Sometimes letting go (resetting) is better than holding on.
  • You’re only as strong as your current streak.
  • It’s okay to start over — if the future looks better.

🧠 Final Thoughts

Kadane’s Algorithm is a rare mix of greedy and optimal. It’s intuitive, efficient, and forms the basis for solving a wide variety of problems in DSA and real-world apps.

If you’re preparing for coding interviews, this is one of the top 5 patterns you MUST master.