# Why does Kadane's algorithm solve the maximum sub-array problem?

I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms".

it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], A[i+1] , ... , A[j] in given array A , ... , A[n].

The exercise is about developing linear-time algorithm to solve this using a following idea, (f.y.i. A[1 ,... , j] means A , A , ... , A[j] )

Knowing a maximum sub-array of A[1, ... , j], extend the answer to find a maximum sub-array ending at index j+1 by using the following observation: a maximum sub-array of A[1, ... , j+1] is either a maximum sub-array of A[1,...,j] or a sub-array A[i,...,j+1], for some 1 <= i <= j+1. Determine a maximum sub- array of the form A[i,...,j+1] in constant time based on knowing a maximum sub- array ending at index j." .

People said that this solution is actually Kadane's algorithm, which is relatively a simple algorithm stated on Wikipedia (I'm really sorry that you have to move to another site. but it explains better than I do.)

However, Kadane's Algorithm deals with only a sub-array that ends at exactly j. but above idea says I should use maximum sub-array of A[1, ... , j] and we can't guaranteed that this sub-array should end with j. Because I think this two algorithm is quite different.

Suppose $A[1..N]$ is your array for which you want to find maximum sum sub-array. Construct $B[1..N]$ such that $B[j]=max (\sum A[k] \mid k \le j,k \ge i)$ ($i$ is some starting index for which B[j] is maximum). So it boils down to $B[j]=max(B[j-1]+A[j],A[j])$ (here I am assuming that empty sub-array isn't allowed in answer). And then find the maximum $B[j]$ for all $j \in [1..N]$. Now this can be done in constant space since we only need result of the previous iteration( for $j$ we need only $B[j-1]$) and the maximum sub-array sum which has occurred till now. Now compare these two ideas and you will get you answer.
• The second idea which used constant space is Kadane's Algorithm. Maximum sum subarray for $A[1..j]$ is not $B[j]$ but $max(B[k] \mid k \le j)$ . $B[j]$ is only max subarray sum ending at $j$. – preetsaimutneja Jun 23 '15 at 6:05
• The first algorithm that I used doesn't take advantage of this but the second one (Kadane's algorithm) has this stored in the form of max_so_far in the wiki page. – preetsaimutneja Jun 23 '15 at 6:25