最大字段和-分治法

#include "stdafx.h"
#include "iostream"
using namespace std;

int a[1001];
int b[8]={1,-3,7,8,-4,12,-10,6};

int GetMax(int a,int b,int c)
{
	if(a>b)
		if(b>c)
			return a;
		else if(a>c)
			return a;
		else
			return c;
	else if(b>c)
		return b;
	else
		return c;
}

int cmop(int start,int end){
	int x=0;
	int y=0;
	int z=0;
	int sum=0;
	int i,j;
	int n=(start+end)/2;
	for(i=start;i<n;i++)
	{
		x+=b[i];
	}
	for(j=n;j<end;j++)
	{
		y+=b[j];
	}
	int t1=0;
	int t2=0;
	int rmax=0;
	int lmax=0;
	int kstart,kend;
	for(int k=0;k<n;k++){
		
		if(t1+b[n-k-1]>rmax)
		{
			rmax=t1+b[n-k-1];
			kstart=n-k-1;
		}
		
		if(t2+b[n+k]>lmax)
		{
			lmax=t2+b[n+k];
			kend=n+k;
		}

		t1+=b[n-k];
		t2+=b[n+k];
	}
	z=rmax+lmax;
	return GetMax(x,y,z);
	
}

int Maxsum(int n){

	int sum=0;
	int b=0;
	for(int i=0;i<n;i++){
		if(b>0) b+=a[i];
		else{
			b=a[i];
		}
		if(b>sum) sum=b;
	}
	return sum;
}



int main()
{
	int a=0;
	
	cout<<cmop(0,8)<<endl;

	system("pause");
	return 0;
}