對原問題有如下解 1.最大子序列在數(shù)組中點(diǎn)的左邊 2.最大子序列在數(shù)組中點(diǎn)的右邊 3.最大子序列跨越數(shù)組中點(diǎn)
#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);}新聞熱點(diǎn)
疑難解答
