Divide and Conquer - Maximun subarray
===

## Divide and Conquer:
1. 先將問題切成很多相同的子問題。(Divide)
2. 解決每個子問題。(Divide)
3. 合併每個解。(Conquer)

## Maximun subarray(pseudocode)

FIND-MAX-CROSS-SUBARRAY(A, low, mid, high)
left-sum = -inf
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if(sum > left-sum)
        left-sum = sum
        max-left = i
        
right-sum = -inf
sum = 0
for j = mid + 1 to high
    sum = sum + A[i]
    if(sum > right-sum)
        right-sum = sum
        max-right = j
return (max-left, max-right, left-sum + right-sum)

FIND-MAXIMUN-SUBARRAY(A, low, high)
if high==low
    return (low, high, A[low])
else mid = [(low+high)/2]
    // find max left-sum 
    (left-low, left-high, left-sum) = FIND-MAXIMUN-SUBARRAY(A, low, mid)
    // find max right-sum 
    (right-low, right-high, right-sum) = FIND-MAXIMUN-SUBARRAY(A, mid + 1, high)
    // find max cross-sum
    (cross-low, cross-high, cross-sum) = FIND-MAX-CROSS-SUBARRAY(A, low, mid, high)
    if left-sum >= right-sum and left-sum >= cross_sum
        return (left-low, left-htgh, left-sum)
    else right-sum >= left-sum and right-sum >= cross-sum
        return (right-low, right-high, right-sum)
    return (cross-low, cross-high, cross-sum)