最大子段和的简单算法.cpp

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

//最大子段和的简单算法

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

int MaxSum(int n, int a[], int &besti, int &bestj)
{
	int i,j,k,sum=0;
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
		{
			int thissum=0;
			for(k=i; k<=j; k++) thissum+=a[k];
			if (thissum>sum)
			{
				sum=thissum;
				besti=i+1;
				bestj=j+1;
			}
		}
	return sum;
}

/*简单算法的改进
int MaxSum(int n, int a[], int &besti, int &bestj)
{
	int i,j,sum=0;
	for(i=0; i<n; i++)
	{
		int thissum=0;
		for(j=i; j<n; j++)
		{
			thissum+=a[j];
			if (thissum>sum)
			{
				sum=thissum;
				besti=i+1;
				bestj=j+1;
			}
		}
	}
	return sum;
}
*/

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