The O(n) Club: Maximum Subarray — Kadane’s Algorithm for Hot Streaks Only

The O(n) Club: Maximum Subarray — Kadane’s Algorithm for Hot Streaks Only

⚡ TL;DR

You want the largest sum you can get by picking a *contiguous* slice of an integer array — no skipping elements, no daydreaming. Brute force takes forever, but Kadane’s Algorithm gives you the answer in one smooth sweep. Here’s what you should absolutely NOT write:

// Avoid: This brute-force approach is about as fun as a surprise production outage
public int maxSubArrayBrute(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

🧠 How Devs Usually Mess This Up

First, people forget that ‘subarray’ means contiguous. You can’t just pick your favorite numbers as if you’re at a buffet — it’s more like being forced to eat every donut from one side of the box to the other. Also, many try to track both the sum and indices (the interview only wants the sum, not a family photo). And if you copy max(0, ...) logic from some random blog, congrats: your code will fail if all numbers are negative. Don’t be that dev.

🔍 What’s Actually Going On

Here’s Kadane’s in a nutshell: You’re walking across an emotional minefield (the array), and any time your running total goes negative, your self-respect says, “Let’s pretend that drama never happened and start over.” At each step, you either extend your streak or start fresh, always keeping track of your best mood so far. Finance nerds use this for stocks. Genomics folks do it with DNA. Developers just use it to feel smart in interviews.

🛠️ PseudoCode

• Initialize: Set both maxSum and currSum to the first number.
• Iterate over the rest:
  • For each element, choose: continue current streak (currSum + current), or launch a new one (current alone).
  • currSum = Math.max(nums[i], currSum + nums[i]);
  • Update the highest sum: maxSum = Math.max(maxSum, currSum);
• Result: Return maxSum.

// Kadane-ized Java
int maxSum = nums[0];
int currSum = nums[0];
for (int i = 1; i < nums.length; i++) {
    currSum = Math.max(nums[i], currSum + nums[i]);
    maxSum = Math.max(maxSum, currSum);
}
return maxSum;

💻 The Code

public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int currSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currSum = Math.max(nums[i], currSum + nums[i]);
        maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All numbers negative? Kadane’s still works — returns the least-terrible number. No need to cheat with zero.
• Don’t treat subarray like a subsequence — no hopping, no picking favorites.
• If you write currSum = Math.max(0, currSum + nums[i]), your code will burst into flames if the whole array is negative. (OK, just wrong answers — but still.)
• One loop, O(n) time. One variable for max, one for current. O(1) space. Minimalist, like a monk with a calculator.

🧠 Interviewer Brain-Tattoo

“When your current streak gets negative, walk away and start fresh. That’s Kadane’s Algorithm: emotional resilience, but make it arrays.”