分治法之求最大连续子序列和

对原问题有如下解 1.最大子序列在数组中点的左边 2.最大子序列在数组中点的右边 3.最大子序列跨越数组中点

#include<iostream> using namespace std; int FIND_MAX_CROSSING_SUBARRAY(int a[],int low,int high) { int mid = (low+high)/2; int i = mid; int j = mid+1; int left_sum = 0; int right_sum = 0; int sum = 0; while(i>=low){ sum += a[i]; if(sum>left_sum) left_sum = sum; i--; } sum = 0; while(j<=high){ sum += a[j]; if(sum>right_sum) right_sum = sum; j++; } return left_sum+right_sum; } int FIND_MAXIMUM_SUBARRAY(int a[],int low, int high) { if(low == high) return a[low]; int mid = (low+high)/2; int left_sum = FIND_MAXIMUM_SUBARRAY(a,low,mid); int right_sum = FIND_MAXIMUM_SUBARRAY(a,mid+1,high); int cross_sum = FIND_MAX_CROSSING_SUBARRAY(a,low,high); if(cross_sum>left_sum && cross_sum>right_sum) return cross_sum; if(left_sum>cross_sum && left_sum>right_sum) return left_sum; if(right_sum>left_sum && right_sum>cross_sum) return right_sum; } int main() { int a[10] = {-1,0,23,414,-231,11,4234,-131323,1321,321}; cout<<FIND_MAXIMUM_SUBARRAY(a,0,9); }