Computer Science is one of the subjects where professional coders are creating various technical concepts for everyday life benefits. Take for example a smartphone. Without coding, our smartphones won’t run; this is how important programming is.

Speaking of coding, nothing works without an algorithm. Notably, there are plenty of algorithms, each serving its unique purpose. 

In this article, we will look specifically at Kadanes algorithm since, in interviews, questions related to this algorithm are often asked. 

Kadane’s algorithm is a type of dynamic programming used to solve problems related to finite-dimensional nonlinear questions such as maximum subarray sum.

To better understand this comprehensive algorithm, let’s learn about dynamic programming first. Take a look. 

What is dynamic programming?

Dynamic programming is a technique that breaks a programme into smaller ones and saves the result for later use without recalculating it. Simply said, dynamic programming breaks down a problem into subproblems, then answers each of those sub-problems to get the final answer. In this way, the answers can be saved and will help us to avoid re-calculations.

There are two important types of dynamic programming that are,

Top-Down approach: Employs memoization (recursion).

Bottom-up approach: The tabulation approach is used and recursion is avoided while still addressing the same kind of problems.

Under this programming technique, Kadane’s algorithm is an iterative dynamic programming type (top-down approach) and now let’s understand what that algorithm is all about. 

What is Kadane’s algorithm?

Joseph Born Kadane, a mathematician known as one of the important supporters of Bayesian statistics created Kadane's algorithm. 

The algorithm was presented in a seminar at Carnegie Mellon University to solve the Largest Subarray Problem. 

Moreover, this is a simple example of Dynamic Programming, which is the process of recursively breaking down a large problem into simpler subproblems.

Kadane's Algorithm has the advantage of providing an optimal solution to the Largest Subarray Problem.

What is a maximum subarray problem?

The main need of this problem is to figure a sub-array that has the maximum value compared to all the subarrays that are within an array. Once we find it, we should return it. 

In this problem, negative numbers will also be present so that must be taken into account. 

Here’s an example to understand it better.

Example:

Array 1:  [2, -4, 3, -1, 2]

The subarray that has the maximum sum would be [3, -1, 2]  because 3 - 1 is 2 and 2 + 2 is 4. 

To solve this problem, two methods are used, namely, Brute force and Kadane's algorithm. Let us look at both the approaches to understand why Kadane’s method is the best one. 

Brute Force Method

With the same problem stated above as an example, let’s see how the brute approach works. In this approach, all the subarrays will be found and each subarray’s sum will be counted to find the one with the maximum sum. 

We will begin with the item at index 0 and determine the total of all possible subarrays for that item. Then, starting with the item at the first index, we will determine the total of every subarray. We will repeat this process until we have checked all subarrays.

This strategy examines all available subarrays, which implies that if the array is n size, the time-complexity would be O(n2), and it denotes that too much time gets used. How so? 

Since  we know that an array with n items has n(n+1)/2 subarrays, the brute-force technique will look for all of them n2 times. Hence a lot of time gets utilized.

Kadane’s Algorithm 

Kadane’s method also involves brute force but in reverse. Let’s take another example to understand this method.

Example:

Array: {-2,1,-3,4,-1,2,1,-5,4}

To find the maximum subarray sum we will follow these steps. In the beginning, we will given with the below values: 

msf - maximum so far

meh - maximum sum. This ends at the ith position.

start - to obtain the initial position of ans's subarray

end - to obtain the finishing index of ans's subarray.

Then we proceed with array traversal from the start and input the given ith item to meh. We would then verify whether inserting the ith item yields a bigger value than msf. If so, we will modify our msf as well as the initial and final indexes. Note that the initial index’s value is zero.

for(int i=0;i<nums.size();i++){ 

    meh+=nums[i]; 

    if(meh>msf){ msf=meh; start=s; end=i; } 

    if(meh<0){meh=0; s=i+1;} 

} 

Next we will use the initial and final values to output the answer subarray. Finally, we will return the greatest maximum subarray sum which is the msf.

For the array {-2,1,-3,4,-1,2,1,-5,4} the output would be 

Subarray {4 -1 2 1} and the max sum would be 6.

The time complexity will be O(n) meaning that no extra time was used. How so?  As we know Kadane’s rule comes under dynamic programming we should note that it uses optimal substructures. Due to this, the traversal of the array happens only once unlike brute force where the process keeps getting repeated until the answer is found. Hence the time taken won’t be too much.

Additional Learning

Now that we’re done with Kadane’s algorithm, here's an extra concept to prepare for your interview. Often, recruiters ask coders about linked lists as they’re very popular. Have you ever wondered how in mobile phones we can swipe images from left to right? It is because they’re a linked list. Apart from this, there are plenty of applications of linked list such as 

• Song playlists
• Stacks and queues
• Polynomials
• Next and previous buttons 

You can visit our website to learn more about applications of linked lists to learn about the methods under this problem.

Conclusion

Kadane’s algorithm is a breakthrough in coding since it helped programmers to find maximum subarray without having to waste time that often crashes the computer.

We hope you have got the best insight about this topic. Read more resources like this on our website for further preparation.