最大子段和分治算法.cpp

动态规划解一系列经典问题

//最大子段和分治算法

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define N 10

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,lefts=0;
		for (int i=center; i>=left; i--)
		{
			lefts+=a[i];
			if (lefts>s1) s1=lefts;
		}
		int s2=0,rights=0;
		for (i=center+1; i<=right; i++)
		{
			rights+=a[i];
			if (rights>s2) s2=rights;
		}
		sum=s1+s2;
		if (sum<leftsum) sum=leftsum;
		if (sum<rightsum) sum=rightsum;
	}
	return sum;
}

void main()
{
	srand(time(0));
	int i,a[N];
	for(i=0; i<N; i++)
	{
		a[i]=rand()%999-400;
		cout<<a[i]<<'\t';
	}
	cout<<endl;
	int k=MaxSubSum(a, 0, N-1);
	cout<<k<<endl;
}