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[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 &lt;= i &lt;= 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.