Maximum Subarray Sum: Kadane's Algorithm

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.

Read More