5_39.cpp

C++程序设计技能百练随书配套光盘的源码

# include<iostream.h>
int MaxSubSum(int a[],int left,int right)
{
	int sum=0;
	if(left==right) sum=a[left]>0?a[left]:0;
	else
	{
		int center=(left+right)/2;
		int leftsum=MaxSubSum(a,left,center);
		int rightsum=MaxSubSum(a,center+1,right);
		int s1=0;
		int lefts=0;
		for(int i=center;i>=left;i--)
		{
			lefts+=a[i];
			if(left>s1) s1=lefts;
		}
		int s2=0;
		int rights=0;
		for(int j=center+1;j<=right;j++)
		{
			rights+=a[j];
			if(rights>s2) s2=rights;
		}
		sum=s1+s2;
		if(sum<leftsum) sum=leftsum;
		if(sum<rightsum) sum=rightsum;
	}
	return sum;
}

int MaxSum(int n,int a[])
{
	return MaxSubSum(a,1,n);
}

void main()
{
int arrSize;	//元素的个数
int * arr,i,ss;
cout<<"Please enter the number of array elements:";
cin>>arrSize;		//临时分配元素的个数
arr=new int[arrSize];		//临时分配这些元素所需的内存空间（堆内存中）
if(arr!=NULL)		//判断，堆空间不够分配时，系统会返回一个空指针值NULL
{
		cout<<"\nPlease enter the array elements:\n";
		for (i=0;i<arrSize;i++)		//逐个输入数组元素
			cin>>arr[i];
		cout<<endl;
		for (i=0;i<arrSize;i++)		//显示数组元素
			cout<<arr[i]<<"  ";	// arr[i] 可替换为*(arr+i)
		cout<<endl;
		ss=MaxSum(arrSize,arr);
        cout<<"最大子段和为："<<ss<<endl;
		delete[]arr;			//释放堆内存
}
else
		cout<<"Can't allocate more memory.\n";
}