A Deep Dive into Kadane’s Algorithm

Every programmer loves a good challenge, especially when it comes to making things faster and more efficient. One classic problem that perfectly captures the art of optimization is the Maximum Subarray Problem. The goal is simple: find the contiguous subarray in a list of numbers that has the largest sum.

At first, this might seem like an easy problem to solve. Just check all the subarrays, right? But as you’ll see, there’s more to it than meets the eye. The fun lies in figuring out how to solve it efficiently.

In this article, we’ll take a step-by-step journey through three different approaches:

1. The Naïve Approach (O(n³)): A simple but slow solution that tries every possible subarray.
2. A Smarter Approach (O(n²)): Cuts down some of the redundant work to save time.
3. Kadane’s Algorithm (O(n)): A lightning-fast solution that’s as clever as it is efficient.

By starting with the simplest solution and working our way up to Kadane’s algorithm, we’ll not only learn how it works but also understand why it’s such a powerful tool in algorithm design.

We will try solving Leetcode problem 53 using these 3 approaches.

APPROACH 1 : Cubic Time complexity

Code:

class Solution {
    public int maxSubArray(int[] nums) {
        return cubicSolution(nums);
    }

    private int cubicSolution(int[] nums) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;

        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                int currentSum = 0;
                for (int i = start; i <= end; i++) {
                    currentSum += nums[i];
                }
                maxSum = Math.max(maxSum, currentSum);
            }
        }

        return maxSum;
    }
}

Step 1: Initialize Variables

• n: Stores the length of the input array nums.
• maxSum: Keeps track of the largest sum of any subarray found so far.
• It is initialized to Integer.MIN_VALUE to ensure any sum of the array will be larger initially.

int n = nums.length;
int maxSum = Integer.MIN_VALUE;

Step 2: Outer Loop for the Starting Point

• This loop (for (int start = 0; start < n; start++)) picks the starting index of the subarray.
• For each value of start, we’ll explore all possible subarrays that begin at this index.

Step 3: Inner Loop for the Ending Point

• This loop (for (int end = start; end < n; end++)) picks the ending index of the subarray.
• By combining start and end, we define a subarray that begins at start and ends at end.

Step 4: Calculate the Current Subarray Sum

• Initialize currentSum to 0.
• Use a third loop (for (int i = start; i <= end; i++)) to calculate the sum of elements in the subarray from start to end.
• Add each element nums[i] to currentSum.

int currentSum = 0;
for (int i = start; i <= end; i++) {
    currentSum += nums[i];
}

Step 5: Update the Maximum Sum

• After calculating the sum of the current subarray (currentSum), compare it with maxSum.
• If currentSum is greater than maxSum, update maxSum.

maxSum = Math.max(maxSum, currentSum);

Step 6: Repeat for All Subarrays

• Continue iterating through all possible starting and ending indices using the nested loops.
• Each subarray is checked, its sum is calculated, and maxSum is updated if necessary.

Step 7: Return the Largest Sum

• Once all subarrays have been considered, maxSum contains the largest sum of any contiguous subarray in nums.
• Return maxSum as the result.

The issue with this approach is evident. There are 3 nested loops which in worst case could take the time complexity all the way up to O(n³).
This is inefficient and on coding platforms like Leetcode, you will face a TLE(Time Limit Exceeded) error.

Get Ankit Kumar’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

So, we move on and try to find a better approach.

APPROACH 2: Quadratic Time complexity

Code:

class Solution {
    public int maxSubArray(int[] nums) {
        return quadraticSolution(nums);
    }

    private int quadraticSolution(int[] nums) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;
        for (int start = 0; start < n; start++) {
            int currentSum = 0;
            for (int end = start; end < n; end++) {
                currentSum += nums[end];
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
}

Step 1: Initialize Variables

• n: Stores the length of the input array nums. This helps determine how many elements the array contains, and we use it for loop boundaries.
• maxSum: This variable will store the largest sum found during the process. It is initialized to Integer.MIN_VALUE to ensure that any subarray sum will be larger initially.

Step 2: Outer Loop — Start of the Subarray

• The outer loop (for (int start = 0; start < n; start++)) iterates through each possible starting index of the subarray, from start = 0 to n-1.
• currentSum: A variable initialized to 0 for each new starting point (start). It keeps track of the sum of the current subarray as we extend it by adding new elements from the end index.

Step 3: Inner Loop — End of the Subarray

• The inner loop (for (int end = start; end < n; end++)) runs from start to n-1, iterating through each possible ending index of the subarray.
• currentSum += nums[end]: This line adds the value of nums[end] to currentSum, effectively extending the subarray by adding one more element to the right. For each end, the subarray starts from start and grows until end.
• maxSum = Math.max(maxSum, currentSum): After each extension of the subarray, we check if the sum of the current subarray (currentSum) is greater than the previously found maximum (maxSum). If so, maxSum is updated to the new value.

Step 4: Repeat for All Subarrays

• The outer loop (start) moves from the first element to the last element of the array. For each start, the inner loop (end) explores all subarrays that begin at start and end at end.
• For every combination of start and end, the sum is calculated, and maxSum is updated if a larger sum is found.

Step 5: Return the Result

• After checking all possible subarrays, the method returns maxSum, which contains the largest sum found among all contiguous subarrays.

This is a better approach than the previous one because this runs in O(n²) time. However, this is still not very efficient and yet again, you will face a TLE error.

So, finally, we go for a more refined and ingenious approach to this problem based on Dynamic Programming. We use Kadane’s Algorithm.

APPROACH 3: Kadane’s Algorithm

So, how does this work?
The idea is simple. It works by iterating through the array once while maintaining two values: the current sum of the subarray being considered and the maximum sum found so far. As we go through the array, we keep adding each element to the current sum. If the current subarray sum becomes negative, we will restart from the current element. The maximum sum is updated whenever the current sum exceeds it. By the end of the loop, the algorithm returns the largest sum of any contiguous subarray, and it does so in linear time, O(n), making it much faster than brute-force methods.

Code:

class Solution {
    public int maxSubArray(int[] nums) {
        return kadaneAlgo(nums);
    }

    private int kadaneAlgo(int[] nums) {
        int maxx = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum = Math.max(sum + nums[i], nums[i]);
            maxx = Math.max(maxx, sum);  
        }

        return maxx;
    }
}

Step 1: Initialization

int maxx = nums[0];
int sum = nums[0];

• maxx: This variable stores the largest sum encountered during the traversal of the array. It is initialized to nums[0] (the first element in the array).
• sum: This variable keeps track of the sum of the current subarray being considered. It is also initialized to nums[0] to start with the first element.

Step 2: Loop through the Array

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

• The loop starts at index 1 (the second element) because we’ve already initialized maxx and sum to the first element.

Step 3: Update sum

sum = Math.max(sum + nums[i], nums[i]);

• sum + nums[i]: This represents adding the current element nums[i] to the sum of the previous subarray. If the sum is positive, it would be beneficial to include this element in the subarray.
• nums[i]: This represents starting a new subarray with just the current element, effectively resetting the sum if continuing the current subarray results in a negative sum.
• Math.max(sum + nums[i], nums[i]): This ensures that we either extend the current subarray or start fresh from the current element. If the sum of the current subarray becomes negative, we start a new subarray starting at nums[i].

Step 4: Update maxx

maxx = Math.max(maxx, sum);

• After updating sum, this line updates maxx to be the maximum of the current maxx (the largest sum found so far) and the new sum. This ensures that maxx always holds the largest sum of any subarray encountered up to that point.

Step 5: Return the Result

return maxx;

• After the loop finishes iterating through the entire array, maxx holds the maximum sum of any contiguous subarray, which is then returned as the result.

This implementation of Kadane’s algorithm works in linear time O(n) and efficiently finds the largest sum of any contiguous subarray.

Conclusion

And there you have it! Kadane’s Algorithm — a neat and clever way to find the maximum sum of a contiguous subarray. It’s fast, efficient, and makes coding seem easy when you see it working in just one pass through the array. Unlike those slow brute-force solutions, Kadane’s algorithm swoops in with its O(n) magic, and before you know it, you’ve got the largest subarray sum in no time!

If you ever find yourself faced with a similar problem, you’ll know exactly where to turn. What’s even better? The principles behind Kadane’s Algorithm are flexible enough that you can use them for even more complex problems (hello, multidimensional arrays!).

So, next time you’re dealing with arrays, subarrays, or any problem that asks for the “biggest” or “best” thing, give Kadane’s algorithm a try. Play around with it, implement it in different languages and have fun.

Happy Coding :)