- #include
- using namespace std;
- /*分治法解决最大子序列问题*/
- intMaxSubSum(const inta[],intleft,int right);
- int main(){
- freopen("input.txt","r", stdin);
- inta[100];
- int num;
- intlength =0;
- while(cin >> num){
- a[length++] = num;
- }
- cout << MaxSubSum(a,0, length-1) << endl;
- }
- intMaxSubSum(const inta[],intleft,int right){
- int maxLeftSum, maxRightSum;
- intmaxLeftBorderSum =0, maxRightBorderSum =0;
- intleftBorderSum =0, rightBorderSum =0;
- intcenter = (left + right)/2;
- //基准情况
- if(left == right){
- if(a[left] >0)
- return a[left];
- else
- return 0;
- }
- //递归调用子序列(进行分治) maxLeftSum = MaxSubSum(a, left, center);
- maxRightSum = MaxSubSum(a, center+1, right);
- //跨越中间的最长子序列和
- for(inti=center; i>=left; i--){
- leftBorderSum += a[i];
- if(leftBorderSum > maxLeftBorderSum){
- maxLeftBorderSum = leftBorderSum;
- }
- }
- for(inti=center+1; i<=right; i++){
- rightBorderSum += a[i];
- if(rightBorderSum > maxRightBorderSum){
- maxRightBorderSum = rightBorderSum;
- }
- }
- //求出这三种情况下最大的
- returnmax(max(maxLeftSum, maxRightSum), (maxLeftBorderSum + maxRightBorderSum));
- }
来源: http://www.bubuko.com/infodetail-1949260.html