# Kadane’s Algorithm : How and Why does it Work?

If you are here, then chances are that you were trying to solve the “Maximum Subarray Problem”. And came across Kadane’s Algorithm but couldn’t figure out how something like that is working. You were tired of using Kadane’s Algorithm as a “black-box”. I wanted to understand the dynamic programming aspect of it. Or maybe you just want to learn about a new concept which make better at programming. As a result the reason, you’ve come to the right place.

Then, we would look at a quite popular programming problem, the Maximum Subarray Problem.

#### Dynamic Programming

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems. This is mainly an optimization over plain recursion. Divide & Conquer algorithm partition the problem into disjoint subproblems solve the subproblems recursively. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

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. For example, for the array given above, the contiguous subarray with the largest sum is [4, -1, 2, 1], with sum 6. We would use this array as our example for the rest of this article.