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

				//最大子段和的简单算法
				
				#include 
				#include 
				#include 
				#define N 10
				
				int MaxSum(int n, int a[], int &besti, int &bestj)
				{
					int i,j,k,sum=0;
					for(i=0; i						for(j=0; j						{
							int thissum=0;
							for(k=i; 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					{
						int thissum=0;
						for(j=i; 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					{
						a[i]=rand()%999-400;
						cout					}
					cout					int k=MaxSum(N, a, besti, bestj);
					cout				}