Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?

Dynamic Programming

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map, etc.). So the next time the same sub-problem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time.

Maximum Subarray Problem

The maximum subarray problem is the task of finding the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers.

Maximum Sum Subarray (In Yellow)

Brute Force Approach

One very obvious but not so good solution is to calculate the sum of every possible subarray and the maximum of those would be the solution. We can start from index 0 and calculate the sum of every possible subarray starting with the element A[0], as shown in the figure below. Then, we would calculate the sum of every possible subarray starting with A[1], A[2] and so on up to A[n-1], where n denotes the size of the array (n = 9 in our case). Note that every single element is a subarray itself.

Brute Force Approach: Iteration 0 (left) and Iteration 1 (right)

Kadane’s Algorithm

In this section, we would use the brute force approach discussed above again, but this time we would start backward. How would that help? Let’s see.

Backward Brute Force Approach: Iteration 0 (left) and Iteration 1 (right)

Code Walkthrough

Below is a very much self-explanatory implementation (in C++) of a function which takes an array as an argument and returns the sum of the maximum subarray.

Conclusion

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of dynamic programming. Kadane’s algorithm is able to find the maximum sum of a contiguous subarray in an array with a runtime of O(n).

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rohit Singhal

Rohit Singhal

I find things that I like. And. I do them.