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

				//最大子段和分治算法
				
				#include 
				#include 
				#include 
				#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						{
							rights+=a[i];
							if (rights>s2) s2=rights;
						}
						sum=s1+s2;
						if (sum						if (sum					}
					return sum;
				}
				
				void main()
				{
					srand(time(0));
					int i,a[N];
					for(i=0; i					{
						a[i]=rand()%999-400;
						cout					}
					cout					int k=MaxSubSum(a, 0, N-1);
					cout				}