Kadane’s Algorithm: The One Trick Every Coder Should Know

Have you ever felt overwhelmed by a coding problem that seems too simple, yet too confusing at the same time? Well, let me introduce you to a gem that every coder should have in their toolkit: Kadane’s Algorithm. This isn't just a powerful algorithm—it’s a mindset shift. Once you understand it, you’ll never look at problems the same way again. Ready to dive in? Let’s go! 🏊‍♂️

What Problem Does Kadane’s Algorithm Solve?

Let’s say you’re given an array of integers (which may include negative numbers too), and your task is:

Find the contiguous subarray (subsequence of elements that are next to each other) that has the highest sum.

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

Explanation: The subarray [4, -1, 2, 1] gives the maximum sum = 6

Intuition: Think Like a Problem Solver

Imagine you’re walking down a road where:

• Positive numbers give you energy

• Negative numbers drain your energy

As you walk, you collect energy (sum the numbers). But here’s the catch:

• If your energy ever drops below zero, you drop everything and start fresh from the next step.

That’s the magic of Kadane’s algorithm.
It keeps adding numbers and resets the sum when it becomes negative—because dragging a negative sum into your future will only make things worse!

Why Does It Work?

It’s based on a simple, greedy idea:

• If the current sum becomes negative, it will only hurt future subarrays.

• So we start fresh from the next number.

This greedy reset helps us build the best possible subarray as we move along.

The Code (C++)

#include <iostream>
#include <vector>
#include <climits>

int maxSubArray(std::vector<int>& nums) {
    int maxSum = INT_MIN;
    int currentSum = 0;

    for (int num : nums) {
        currentSum += num;                      // Add the current number
        maxSum = std::max(maxSum, currentSum);  // Update maxSum if needed
        if (currentSum < 0) currentSum = 0;      // Reset if sum becomes negative
    }

    return maxSum;
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    std::cout << "Maximum subarray sum is: " << maxSubArray(nums) << std::endl;
    return 0;
}

Time & Space Complexity

• Time Complexity: O(n)
  We traverse the array just once. Super fast!

• Space Complexity: O(1)
  Only a few variables used—no extra data structures.

In One Line

• Keep adding numbers.

• Reset when the sum goes negative.

• Track the max at every step.

  Boom, You are done

If you enjoyed this article, share it with your coding buddies or drop a comment!

Happy Coding! 💻✨