假设存在一个这样的数组array，需要求出它的连续子数组，使得该子数组的和最大。

例如这样的一个数组：1, -2, 3, 10, -4, 7, 2, -5 最大子数组： 3，10，-4，7，2

暴力法

不做任何优化，直接枚举所有的情况。 思路：直接算出array[i,…j]的值

int max_sum_array(int *array, int n) { int i,j,k; int sum_max=0,array_sum=0; for(i=0;i<n;i++) { for(j=i;j<n;j++) { for(k=i;k<j;k++){ array_sum+=array[k]; } if(array_sum>=sum_max) sum_max=array_sum; array_sum=0;//重新计算必须清零 } } return sum_max; }

时间复杂度为 O(n3) O ( n 3 ) ，嵌套三成循环。

分治法

这里我们将数组左分，右分开，和跨立在左右之间

int max_sep_array(int *array, int start, int end) { if(start==end) return array[end]; int middle=(start+end)/2; int left_sum=max_sep_array(array,start,middle); int right_sum=max_sep_array(array,middle+1,end); int i,left=array[middle],now=array[middle]; for(i=middle-1;i>=start;i--){ now+=array[i]; left=max(now,left); } int right=array[middle+1]; now=array[middle+1]; for(i=middle+2;i<=end;i++){ now+=array[i]; right=max(now,right); } int sum_max=right+left; return max(max(left_sum,right_sum),sum_max); }

这里的关键在于，当跨立在中间时，数可能是在往左一点，也可能往右一点，一定是从中间往两边发散，一定是从中间。

分析法

动态规划