# Why Kadane's algorithm works?

Kadane’s Algorithm, aka Maximum Sum of Subarray, is an interesting algorithm problem that can be solved with different approaches. This problem is a nice and intuitive question to learn more about Dynamic Programming.

## Maximum Subarray Problem

From Wikipedia:

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array, a[1…n], of numbers which has the largest sum.

The task is to find a subarray (contiguous elements) of the given array that has the largest sum. For instance:

```
[1, 5, -1, 0, 10]
```

The answer would be `[10]`

.

```
[0, -1, -5, 0, -4]
```

The answer would be `[0]`

and so on.

## Solutions

We are going to explore two solutions to attack this problem: Brute-force and Dynamic Programming.

### Brute-force

Using brute-force to solve this problem is trivial. All you need is going through all sub-arrays, keep the global maximum and compare.

But I don’t think this is a clever answer. Or more broadly, brute force is not a clever answer most of the times.

### Dynamic Programming (Kadane’s Algorithm)

Kadane’s algorithm is the answer to solve the problem with `O(n)`

runtime complexity and `O(1)`

space.

Following function shows the Kadane’s algorithm implementation which uses two variables, one to store the local maximum and the other to keep track of the global maximum:

```
def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
```

So we assume that the largest subarray is the first element, then we go through `A[1:]`

elements (all elements except first one). At each step, what we do is:

- Can
*current element plus the last largest sum*help to find a largest subarray (line 4)? - If yes, update the
`max_ending_here`

or our local maximum, otherwise current element is the largest subarray (array of one). - Then update the global maximum or
`max_so_far`

if there is a new global maximum.

When the loop is over, return the global maximum.