分治策略：最大子数组

暴力算法：数组区间位置两两组合，计算组合区间的和值，取最大值。共有种情况，数量级为，每词计算区间之和时间复杂度为，总的时间复杂度为
分治算法：最大子区间落在左半区间，或者右半区间，或者跨越左右区间。按这三种情况划分子问题。
落在左半区间或者右半区间，仍然可以按照这三种情况划分子问题。
跨越左右半区的，从中点位置，向左（右）累加，记录累加和最大的值和位置。之后合并左右最大值。返回。

find_max_crossing_subarray(A,low,mid,high)
left_sum = Minus infinity
sum = 0
for i = mid downto low
  sum = sum + A[i]
  if sum > left_sum
    left_sum = sum
    max_left = i
right_sum = Minus infinity
sum = 0
for j = mid + 1 to high
  sum = sum + A[j]
  if sum > right_sum
    right_sum = sum
    max_right = j
return (max_left,max_right,left_sum+right_sum)

有了一个线性时间的find_max_crossing_subarray在手，就可以设计求解最大子数组的分治算法的伪代码：

find_maxnum_subArray(A,low,high)
  if high==low   //base case: only one element
    return(low,high,A[low])
  else mid = (low+high)/2
    (left_low,left_high,left_sum) = find_maxnum_subArray(A,low,mid)
    (right_low,right_high,right_sum) = find_maxnum_subArray(A,mid+1,high)
    (cross_low,cross_high,cross_sum) = find_max_crossing_subarray(A,low,mid,high)
    if left_sum >= right_sum and left_sum >= cross_sum: 
      return (left_low,left_high,left_sum)
    elseif right_sum >=left_sum  and right_sum >= cross_sum:
      return (right_low,right_high,right_sum)
    else return (cross_low,cross_high,cross_sum)

C++复现代码

#include<iostream>
using namespace std;
int find_max_crossing_array(int A[],int low,int mid,int high)
{
    int left_sum = 1<<31; // int 32位 最小值
    int left_max_index = -1;
    int iter_sum = 0;
    for(int i=mid;i>=low;i--)
    {
        iter_sum += A[i];
        if (iter_sum > left_sum)
        {
            left_sum = iter_sum;
            left_max_index = i;
        }
    }

    int right_max_index = -1;
    int right_sum = 1<<31;
    iter_sum = 0;
    for(int i=mid+1;i<=high;i++)
    {
        iter_sum += A[i];
        if(iter_sum > right_sum)
        {
            right_sum = iter_sum;
            right_max_index = i;
        }

    }
    int max_sum = left_sum + right_sum;
    return max_sum;
}

int find_max_sub_array(int A[],int low,int high)
{
    if(low == high) return A[low];
    int mid = (low+high)/2;
    int left_max = find_max_sub_array(A,low,mid);
    int right_max = find_max_sub_array(A,mid+1,high);
    int mid_max = find_max_crossing_array(A,low,mid,high);
    if(left_max >= mid_max && left_max >= right_max) return left_max;
    else if (right_max >= mid_max && right_max >=left_max) return right_max;
    else return mid_max;
}
int main()
{
    cout<<"hello world"<<endl;
    int A[5] = {-1,2,3,4,-5};
    int max = find_max_sub_array(A,0,4);
    // int max = find_max_crossing_array(A,0,2,4);
    cout<<"max sub array:"<<max<<endl;
}