The One Algorithm to Conquer Them All: Kadane's Algorithm

Ever stared at a line of code or an algorithm and felt like you were trying to decipher an ancient language? We've all been there. But what if I told you there's a beautifully simple, elegant algorithm that can solve a whole class of array problems, and its core logic is as intuitive as deciding whether to keep your umbrella open in the rain?

Today, we're going on an adventure with one of my favorite algorithms: Kadane's Algorithm. We'll start with a classic Wall Street problem, and then, like any good sequel, we'll add some mind-bending twists.

Grab your favorite beverage, and let's dive in!

The Original Blockbuster: Maximum Subarray

Imagine you're a stock trader. You have a list of the daily price changes of a stock for the last month. Some days it went up, some days it went down.

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

Your goal is to find the most profitable continuous period. In other words, when should you have bought and when should you have sold to make the maximum possible profit?

This is the classic Maximum Subarray Problem. We need to find the contiguous subarray with the largest sum.

The Brute-Force Bummer

Your first instinct might be to check every possible subarray. Start at index 0, find the sum of all subarrays beginning there. Then move to index 1, do the same, and so on. This works, but it's slow. Like, really slow (O(n²)). For a large array, you'd miss the market opportunity while your code is still running!

Enter Kadane's Algorithm: The Elegant Hero

Kadane's insight is pure genius. Let's walk through the array from left to right, keeping track of two things:

1. currentMaxSum: The maximum sum of a subarray ending at the current position.

2. globalMaxSum: The maximum sum found so far, anywhere in the array.

Here's the logic in plain English:

As we look at each number, we ask a simple question: "Does this number help my current subarray, or would I be better off starting a new subarray right here?"

• If my currentMaxSum is positive, the current journey is profitable! Let's add the new number to it.

• If my currentMaxSum has become negative, it's dragging me down. It's a losing streak. I should cut my losses and start a fresh subarray beginning with the current number.

Let's trace it with our example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Element	currentMaxSum Logic	currentMaxSum	globalMaxSum
-2	Start new: max(-2, -2)	-2	-2
1	Add to current: max(1, -2 + 1)	1	1
-3	Add to current: max(-3, 1 + -3)	-2	1
4	Start new: max(4, -2 + 4)	4	4
-1	Add to current: max(-1, 4 + -1)	3	4
2	Add to current: max(2, 3 + 2)	5	5
1	Add to current: max(1, 5 + 1)	6	6
-5	Add to current: max(-5, 6 + -5)	1	6
4	Add to current: max(4, 1 + 4)	5	6

The maximum sum we found is 6. This corresponds to the subarray [4, -1, 2, 1]. See how simple that was? We just walked through the array once!

The Java Code:

code Javadownloadcontent_copyexpand_less

    public int maxSubArray(int[] nums) {
    int globalMaxSum = nums[0];
    int currentMaxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int num = nums[i];
        // Is it better to start a new subarray or extend the old one?
        currentMaxSum = Math.max(num, currentMaxSum + num);

        // Did we find a new all-time high?
        globalMaxSum = Math.max(globalMaxSum, currentMaxSum);
    }

    return globalMaxSum;
}

---

The Sequel: Maximum Sum Circular Subarray

Alright, you've mastered the linear stock market. Now for a twist! What if the market was... circular? Imagine the data represents a year, and December 31st wraps around to connect with January 1st.

arr = [5, -3, 5]

• A normal subarray max is [5, -3, 5], sum = 7.

• But wait! If we wrap around, we can take [5] from the end and [5] from the beginning. That subarray is [5, 5], and its sum is 10!

How do we solve this? There are two possibilities for the maximum sum:

1. Case 1: The Non-Wrapped Subarray. The maximum sum is somewhere in the middle of the array. We already know how to solve this – it's just plain old Kadane's!

2. Case 2: The Wrapped Subarray. The maximum sum "wraps around" the end to the beginning.

This is where the magic happens. A wrapped subarray means we're taking some elements from the start and some from the end. This is the same as taking the TOTAL sum of the array and subtracting the middle part we don't want.

To maximize our wrapped sum, we need to subtract the smallest possible middle part. In other words, we need to find the minimum subarray sum!

So, the logic is:
The answer is max(Kadane's_Max, Total_Sum - Kadane's_Min)

Finding the minimum subarray sum is just a tiny tweak on Kadane's algorithm—instead of Math.max, you use Math.min.

One crucial edge case: What if all numbers are negative, like [-1, -2, -3]?
The totalSum will be -6. The minSubarraySum will also be -6. totalSum - minSubarraySum would be 0, which is wrong. The real answer should be -1. So, if the max sum from the non-wrapped case is negative, that's our answer.

The Java Code:

code Javadownloadcontent_copyexpand_lessIGNORE_WHEN_COPYING_STARTIGNORE_WHEN_COPYING_END

    public int maxSubarraySumCircular(int[] nums) {
    int totalSum = 0;
    int globalMaxSum = nums[0];
    int currentMaxSum = 0;
    int globalMinSum = nums[0];
    int currentMinSum = 0;

    for (int num : nums) {
        // Standard Kadane's for Maximum
        currentMaxSum = Math.max(currentMaxSum + num, num);
        globalMaxSum = Math.max(globalMaxSum, currentMaxSum);

        // Inverted Kadane's for Minimum
        currentMinSum = Math.min(currentMinSum + num, num);
        globalMinSum = Math.min(globalMinSum, currentMinSum);

        totalSum += num;
    }

    // Edge case: if all numbers are negative, globalMaxSum will be the answer
    if (globalMaxSum < 0) {
        return globalMaxSum;
    }

    // The answer is either the non-wrapped max or the wrapped max
    return Math.max(globalMaxSum, totalSum - globalMinSum);
}

---

The Final Chapter: Maximum Product Subarray

You thought we were done? Let's change the game entirely. Instead of sum, let's find the maximum product.

arr = [2, 3, -2, 4]

The maximum product is [2, 3] = 6. Easy.

What about arr = [2, 3, -2, 4, -1]?
The subarray [2, 3, -2, 4, -1] has a product of 48.

Suddenly, negative numbers are our friends! A negative number can flip a very small (negative) product into a very large (positive) one.

This breaks Kadane's original logic. We can't just discard a negative subarray, because it might become a hero later.

The New Strategy

Since a negative number can flip the script, we need to keep track of two things at every step:

1. currentMaxProduct: The maximum product of a subarray ending here.

2. currentMinProduct: The minimum product of a subarray ending here.

Why the minimum? Because if the next number is negative, our currentMinProduct (which is a negative number) could suddenly become our new currentMaxProduct!

At each step i, the new currentMaxProduct will be the maximum of:

1. The current number nums[i] itself (starting a new subarray).

2. The old currentMaxProduct * nums[i].

3. The old currentMinProduct * nums[i] (this is the key!).

The same logic applies to finding the new currentMinProduct.

The Java Code:

code Javadownloadcontent_copyexpand_lessIGNORE_WHEN_COPYING_STARTIGNORE_WHEN_COPYING_END

    public int maxProduct(int[] nums) {
    if (nums.length == 0) return 0;

    int globalMaxProduct = nums[0];
    int currentMaxProduct = nums[0];
    int currentMinProduct = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int num = nums[i];

        // We need a temp variable because we're about to overwrite currentMaxProduct
        int tempMax = currentMaxProduct;

        // Calculate the new max and min for the current position
        currentMaxProduct = Math.max(num, Math.max(tempMax * num, currentMinProduct * num));
        currentMinProduct = Math.min(num, Math.min(tempMax * num, currentMinProduct * num));

        // Update the overall global max
        globalMaxProduct = Math.max(globalMaxProduct, currentMaxProduct);
    }

    return globalMaxProduct;
}

The Journey's End

We started with a simple, brilliant idea and saw how it could be adapted to solve increasingly complex problems. This is the beauty of algorithms. They are not just abstract code; they are problem-solving patterns.

Kadane's algorithm teaches us a powerful lesson in dynamic programming: build up a solution by making the best possible decision at each step, based on the results of the previous step.

So next time you face a tricky array problem, ask yourself: can a little bit of Kadane's magic help?

Happy coding!

---

Tags for Hashnode: #java #algorithms #programming #kadanes-algorithm #coding #interviewprep #datastructures