算法设计8-数列最大字段和问题

参考例题15，P143页

问题描述

代码

#include<iostream>
using namespace std;
int max_sum3(int a[],int n);
int max_sub_sum(int a[],int left,int right)
{//s1=a[i]+...+a[n/2]  s2=a[n/2+1]+...+a[j]int center,i,j,sum,left_sum,right_sum,s1,s2,lefts,rights;if(left==right){if(a[left-1]>0)//若第一个值为负数，则没必要算入，直接舍去（left是编号，应该用下标计算）return a[left-1];elsereturn 0;}else{center=(left+right)/2;//中间的编号left_sum=max_sub_sum(a,left,center);//一开始一直进入函数直到left=center,即left=right，得到一个0后left=1,center=1,right=2再进入right_sum right_sum=max_sub_sum(a,center+1,right);//right_sum的center+1=right一直成立s1=0;lefts=0;for(i=center;i>=left;i--){lefts=lefts+a[i-1];//i是编号，应该用下标计算if(lefts>s1)s1=lefts;}s2=0;rights=0;for(i=center+1;i<=right;i++){rights=rights+a[i-1];if(rights>s2)s2=rights;}if(s1+s2<left_sum&&right_sum<left_sum)return left_sum;if(s1+s2<right_sum)return right_sum;return s1+s2;}
}
int max_sum3(int a[],int n)
{return max_sub_sum(a,1,n);
}
int main()
{int n=6;int a[n]={-2,11,-4,13,-5,-2};cout<<max_sum3(a,n);return 0;
}

运行结果截图