maximum-subarray problem

 If we are given an array A, we now want to find the nonempty, contiguous subarray of A whose values have the largest sum. We call this contiguous subarray
the maximum subarray.

Clean way to illustrate basic algorithm design:
1:  brute force algorithm: O(n^3)
2: algorithm that reuses data: O(n^2)
3: divide-and-conquer algorithm: O(n *lgn)

divide-and-conquer algorithm:
need consider two factors:
1: termination condition
2: combination of left and right .

1: termination condition:
  if(size==1) return;

2: combination
    compare(left, right, combined);
    left and right can be obtained by recursion.
    combined is computed by array[i..mid]+array[mid+1...j];

   array[i..mid]: the max subarray beginning from mid. For example, suppose given  array[0..9]. mid=4; array[i..4] means the max of array[4], array[4,3], array[4,3,2], array[4,3,2,1], array[4,3,2,1,0].



------------------------------------------------------------
Non-recursion solution:
Knowing a maximum subarray of A[1..j], extend the answer to find a maximum subarray ending at index  by using the following observation: a maximum subarray of A[1..j] is either a maximum subarray of A[1..j] or a subarray A[1..j+1]. Determine a maximum subarray of the form A[1..j+1] in constant time based on knowing a maximum subarray ending at index j.