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.