[Solved]: Why does Kadane's algorithm solve the maximum sub-array problem?

Problem Detail: 

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[1] , ... , 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[1] , A[2] , ... , 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.

Asked By : Lee Young joo

Answered By : sai_preet

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43852