Understanding Kadane’s Algorithm

Kadane's algorithm, a well-known algorithm also known as the maximum subarray sum problem involves finding the contiguous subarray with the most significant sum within a given array of numbers. 

Kadane’s Algorithm is an iterative dynamic programming algorithm.

In this blog, we will be reading and learning about "Kadane’s Algorithm" and learning a step-by-step approach to solving this problem along with analysing its time complexity.

This would give you a deeper dive into the concepts involved in solving this very famous algorithmic problem asked in top product based companies. 

But, before that let us know what dynamic programming is!

What Is Dynamic Programming?

Dynamic programming is a problem-solving technique used in computer science and mathematics to efficiently solve problems by breaking them down into overlapping subproblems. 

It is particularly useful for optimisation problems that exhibit the property of overlapping subproblems and optimal substructure.

The key idea behind dynamic programming is to solve each subproblem only once and store the result for future reference.

By doing so, we avoid redundant computations and significantly improve the efficiency of the overall solution.

Dynamic programming typically involves three main steps:

1. Defining the recursive relationship: The problem is divided into smaller, overlapping subproblems, and a recursive relationship is established between the original problem and its subproblems.

2. Formulating the memoization table: A memoization table or array is created to store the solutions of the subproblems. This table is used to store and retrieve previously computed results, preventing redundant calculations.

3. Building the solution bottom-up: Starting from the base cases, the solutions to subproblems are computed and stored in the memoization table. These solutions are then used to derive the solution for the original problem.

Dynamic programming can be implemented using either a top-down approach (memoization) or a bottom-up approach (tabulation).

Memoization involves storing the results of subproblems in a cache, while tabulation involves building the solution iteratively from the smallest subproblems up to the larger ones.

Dynamic programming is widely used in various domains, including algorithms, artificial intelligence, operations research, and bioinformatics.

Some well-known problems that can be solved using dynamic programming include the knapsack problem, the longest common subsequence problem, and the Fibonacci sequence.

Now, since you all have an idea of what dynamic programming is, we will next move on to the problem statement of Kadane’s Algorithm.

Recommended Reading: DSA Preparation - The Ultimate Guide to Crack DSA Interviews

Kadane’s Algorithm

Given an array of integers, find the contiguous subarray (containing at least one element) with the largest sum and return the maximum sum.

Formally, given an array A of size n, we want to find indices i and j (where 0 ≤ i ≤ j < n) such that the sum of elements in the subarray A[i...j] is maximised.

🎯 Kadane’s Algorithm Explained

Now, from the problem statement above, this is very straightforward: we have to find the maximum sum from the subarrays (any contiguous part of that array, which may consist of any number of elements with at least one element in it). 

Now, from this statement, the one thing which would come to your mind would be that we will have to simply sum up all the integers in the array which would give us the maximum sum from the array itself!

But, if there were negative numbers this approach would fail.

For example, consider an array of integers such as,

Here you can see that the maximum sum of a subarray of the above array [1, -3, 2, 1] is [2, 1] with the sum as 3 which is the solution to the given problem.

🎯 Brute Force Approach

Now, let’s try to understand the brute force or the naive approach to this problem, which would be iterating through all the given elements in the array and checking the sum of each subarray, and then returning the largest sum among them.

Let's apply the brute force approach to the array [1, -3, 2, 1].

The first step should be identifying all the subarrays to the given array which are as follows:

[1], [1, -3], [1, -3, 2], [1, -3, 2, 1], [-3], [-3, 2], [-3, 2, 1], [2], [2, 1], [1]

Now, since we don’t miss out any subarrays we can recall that for a given array of size n there are n*(n+1)/2 subarrays.

So, here is the value of n=4, and hence there should be 4*(4+1)/2 i.e. 10 subarrays and we already have all of them! Great!.

Next, we calculate the sum of each subarray which is as follows:

1, -2, 0, 1, -3, -1, 0, 2, 3, and 1. 

Here, we quickly see that 3 is the maximum sum among all of them, hence this would be our solution!

Now, discussing the time complexity of the above approach it would be O(n2), which can be justified from the formulae which give the total number of subarrays for a given array i.e. n*(n+1)/2 where n is the size of the array.

Let’s look at the algorithm for this approach,

🎯 Quick Think

Now, in the above-discussed brute force approach we notice that while calculating the sum of each subarray we set the total current_sum to 0 again, for example in the array [1, -3, 2, 1] after computing the total sum of subarray whose first element is 1 which are as follows:

[1], [1, -3], [1, -3, 2] and [1, -3, 2, 1] we reset the current_sum = 0 and till this step the value of max_sum = 1.

Next computing the sum of each subarray  [-3], [-3, 2] and [-3, 2, 1] we get max_sum = 1, same as the last step because -3, -1 and 0 are all less than 1 (the max_sum).

Again, computing the sum of the next group of subarrays [2], [2, 1], and [1] we get max_sum = 3, this time the value of max_sum is updated because 3 is greater than 1 (the max_sum until the last step).

Hence we have the solution as 3.

What if we avoid the negative value sums we encountered in our last steps and reset the current_sum to 0?Then, we can quickly get the max sum without iterating the array for the second time!

Now, let us look at the optimised approach to this algorithm in your next section.

🎯 Kadane’s Approach

In this section we will be talking about kadane’s algorithmic approach to solving this problem, let us consider the same array of integers that we had in our previous brute force approach.

Now, let’s discuss the algorithm with the above-given array [1, -3, 2, 1].

Taking the first array element which is 1, the value of current_sum becomes 1 here which is more significant than the INT_MIN value so, the value of max_sum becomes 1.

Next, we move on to the next array element which is -3, and the value of current_sum becomes -2, now here we see that the current_sum is less than max_sum and also it is less than 0 (i.e. negative) so, we update the value of current_sum as 0.

Next, we have the array element as 2, and the value of current_sum becomes 2 now here we see that the current_sum is greater than max_sum, so we update the value of max_sum hence it becomes 2.

Next, we have the array element as 1, and the value of current_sum becomes 3 so here we see that the current_sum is greater than max_sum, so we update the value of max_sum hence it becomes 3.

Hence we have the solution as 3.

Now, let us look at the algorithm for this approach,

Kadane’s Algorithm Implementation

Here’s the code of Kadane’s Algorithm in C++,

By applying the kadane’s algorithm above for this array, we get the maximum sum as 3.

Time and Space Complexity Analysis

Looking at the time complexity of Kadane’s Algorithm it is O(n) (where n is the size of the array) with space complexity of O(1) (i.e. constant space).

The time complexity of this algorithm is O(n) because we are traversing the whole array at once, and since we are not allocating any extra space, its space complexity is O(1).

Recommended Reading: How to Prepare for a Technical Interview - 11 Best Practices

Conclusion

So, this was all about Kadane's Algorithm.

We discussed the brute force approach, and the kadane’s approach with its time and space complexities by taking an example.

This algorithm is very popularly asked in coding and technical interview rounds by MAANG, and top product-based companies and startups as well to judge one's problem-solving ability.

Cracking these technical interviews might be a challenging task for many as these problems are based on critical thinking and problem-solving.

So, how can this be done easily?

One effective way to prepare for coding questions is through mentor-led preparation. 

Having a mentor can provide valuable guidance and support throughout your preparation journey. 

A mentor can help you understand the intricacies of coding questions, provide personalised feedback on your solutions, and offer insights into the best problem-solving approaches.

With a mentor's expertise and experience, you can gain deeper insights into the problem-solving process, learn advanced techniques, and improve your coding style.

Connect 1:1 with a MAANG Mentor