学步园

      对于公共子序列和的求法，我们在学习算法的时候都知道基本的有四种，他们的时间复杂度分别为：O(N^3)   /    O(N^2)   /   O(N logN)    /   O(N)  ,对于前面的两种都是for循环的嵌套，时间用的太多，很不实用，这里就不再写了。只写后面的两种，就当是练手了～

第一种： 递归法（分治）

         把现有的子序列分两段，那么它的最长子序列和的产生只能发生于三种情况： （1）在左半部分产生；（2）在右半部分产生；（3）两半部分的和相加得到  。 如 1 -4 3  -1  2 6 -3 4，分段后左边的最大和为：3，右边的最大和为：9，此时他们的整体最大和就由两部分的和构成，为11。

代码：

private static int maxSumRec(int [] a,int left,int right)
	{
		if(left==right)  // 在临界点时，如果数组中的值是小于0的，直接舍掉，如果是正值就直接加上；
			if(a[left]>0)
			    return a[left];  
		    else
			    return 0;
		// 在没有到达基点是做下面的递归运算；
		// 对两边分别做的递归处理；
		int center=(right+left)/2;
		int maxLeftSum=maxSumRec(a,left,center);  // 开始进入递归运算；
		int maxRightSum=maxSumRec(a,center+1,right);
	    
		// 对左右两边和的最大值的处理；
		int maxLeftBorderSum=0,leftBorderSum=0;
		for(int i=center;i>=left;i--) // 从中间向左一直做加运算，求得包含中间左端向左的最大和子序列的和；
		{
			leftBorderSum+=a[i]; 
			if(leftBorderSum>maxLeftBorderSum)
			    maxLeftBorderSum=leftBorderSum;
		}
		
		int maxRightBorderSum=0,rightBorderSum=0;
		for(int i=center+1;i<=right;i++)
		{
			rightBorderSum+=a[i];
			if(rightBorderSum>maxRightBorderSum)
				maxRightBorderSum=rightBorderSum;
		}
		
		return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightSum);
	 }
	
	public static int maxSubSum3(int []a)
	{
		return maxSumRec(a,0,a.length-1);
	}
	
	public static int max3(int a,int b,int c)
	{
		return a>(b>c?b:c)?a:(b>c?b:c); // 返回三个数中最大的那个；
	}

第二种： 动态规划法

代码：  局部最优解构成整体最优解；

public static int maxSumRec(int []a)
	{
		int maxSum=0,thisSum=0;  // maxSum 是要求的最大公共子序列的值；thisSum 是当前得到的序列的和；
		for(int j=0;j<a.length;j++)
		{
			thisSum+=a[j]; // 对当前的thisSum更新；
			if(thisSum>maxSum)
				maxSum=thisSum;  //对当前的maxSum更新；
			else if(thisSum<0)
				thisSum=0;
		}
		return maxSum;
	}

上面的只是本人的学习笔记，错误不可避免，欢迎大家指正！