问题描述：给定一个数组a，数组中的元素有正数也有负数，数组中的一个或连续多个数组成一个子数组。求这些所有子数组的最大和。例如：a={1, 2, 3, 10，-4,  7，2，-5}，它的最大和应该是：3+10+(-4)+7+2=18。

• 直接法

  • 直接求解A[i,…j]的值：
  • 0≤ i < n
  • i≤ j < n
  • i,i+1…,j-1,j的最大长度为n
  • 因此：时间复杂度O(n3)

• 分治法

  • 将数组从中间分开，那么最大子数组要么完 全在左半边数组，要么完全在右半边数组，要么跨立在分界点上。
  • 完全在左数组、右数组递归解决。
  • 跨立在分界点上：实际上是左数组的最大后 
    缀和右数组的最大前缀的和。因此，从分界点向前扫，向后扫即可。
  • 时间复杂度：T(n) = Ο(nlogn)

• 动态规划法

  • 记S[i]为以A[i]结尾的数组中和最大的子数组
  • 则：S[i+1] = max(S[i]+A[i+1], A[i+1])
  • S[0]=A[0]
  • 遍历i： 0≤i ≤n-1
  • 动态规划：最优子问题
  • 时间复杂度：O(n)

#include <iostream>
#include <stdio.h>
#include <windows.h>
using namespace std;
int MaxSubArray(int *A, int n);
int MaxSubArray2(int *A, int n);
int MaxSubArray3(int *a, int from, int to);
int main(){
	int A[8] = {1,-2,3,10,-4,7,2,-5};
    int result = MaxSubArray(A, 8);
    int result2 = MaxSubArray2(A, 8);
    int result3 = MaxSubArray3(A, 0, 7);
	cout<<"The directed mothod:"<<result<<endl<<"The divide-and-conquer mothod:"<<result2<<endl<<"The planning mothod:"<<result3<<endl;
	return 0;
}

//The directed mothod
int MaxSubArray(int *A, int n){
	int maxSum = A[0];
	int currSum;
	for(int i = 0; i<n; i++){
		for(int j = i; j<n; j++){
			currSum = 0;
			for(int k = i; k<j; k++){
				currSum += A[k];
			}
			if(currSum>=maxSum)
			maxSum = currSum;
		}
	}
    return maxSum;
}

//The divide-and-conquer mothod
int MaxSubArray2(int *A, int n){
	int result = A[0];
	int currSum = A[0];
	for(int i=1; i<n-1; i++){
		if(currSum>=0){
           currSum += A[i];
		}else{
           currSum = A[i];
		}
	}
	if(A[n-1]>=0)
		currSum += A[n-1];
	if(currSum>result)
		result = currSum;
}

//The planning mothod
int MaxSubArray3(int *a,int from,int to){
    if(to ==  from)
    return a[from] ;
      int middle = (from+to)/2;
      int m1 = MaxSubArray3 (a, from, middle);
      int m2 = MaxSubArray3 (a, middle+1, to); 

    int i, left = a[middle], now = a[middle];
    for(i = middle-1; i >= from; --i){
    	now += a[i];
    	left = max(now, left);
    }
       int right = a[middle+1];
       now = a[middle+1];
    for(i = middle+2; i <= to; ++i){
       now += a[i];
       right = max(now,right);
   }
      int m3 = left+right;
      return max(m1, max(m2, m3));
}

运行结果如下：