文章目录

最大子序列问题

给定（可能有负的）整数A1，A2，…，AN，求 ∑ k = i j A k \sum_{k=i}^j A_k ∑k=ij​Ak​的最大值。（为了方便起见，如果所有整数均为负数，则最大子序列和为0）。

算法一：遍历大法

分析

时间复杂度O(N3)

代码

/** * 遍历大法 * Cubic maximum contigugou subsequence sum algorithm. * @param a * @return */
	public static int maxSubSum1(int[] a ) {
		int maxSum=0;
		
		for(int i=0 ;i<a.length ;i++) { //从哪里加？
			for(int x=i; x<a.length ; x++) { //加到哪里？
				int sumTemp = 0 ; 
				for(int s=0 ; s<x-i; s++) { //开始加
					sumTemp+=a[i+s]; //加的结果
					if(sumTemp>maxSum) { //比较
						maxSum = sumTemp; //存下最大的
					}
				}
			}
		}
		
		return maxSum;
	}

算法二：遍历大法（优化）

分析

注意到： ∑ k = i j A k \sum_{k=i}^j A_k ∑k=ij​Ak​ = Aj + ∑ k = i j − 1 A k \sum_{k=i}^{j-1} A_k ∑k=ij−1​Ak​
新代码避免重复累加

代码

/** * 优化遍历算法 * @param a * @return */
	public static int maxSubSum2(int[] a) {
		int maxSum =0 ; 
		
		for(int i=0 ; i<a.length ; i++) {//从哪里加？
			int tempSum = 0 ; 
			for(int x=i ; x<a.length; x++) { //直接加了
				tempSum+=a[x];
				if(tempSum>maxSum) {
					maxSum = tempSum;
				}
			}
		}
		
		return maxSum ; 
	}

算法三：分治（divide-and-conquer）

分析

把数组分为左右两部分和跨越两边的中间部分，左边和右边的最大子序列用递归得出，中间的子序列在代码中完成，最后返回三部分的最大的最大子序列。
这就完成了本区域的任务，更下区域的任务由递归完成。
所以，递归的调用总是对小于原问题的问题进行的。

代码

/** * 算法3：“分治”策略 * * Note： * 专门写个驱动，可能是嵌套需要特定的固定的参数吧。 * * Driver for divide-and-conquer maximum contiguous * subsequence sum algorithm * @param a * @return */
	public static int maxSubSum3(int[] a ) {
		return maxSumRec(a,0,a.length-1) ;
	}
	public static int maxSumRec(int[] a,int left,int right ) {
		if(left>=right){ //base case
			if(a[left]>0) {
				return a[left] ; 
			}else {
				return 0 ;
			}
		}
		//递归
		int center = (left+right)/2 ;
		int maxLeftSum = maxSumRec(a, left, center);
		int maxRightSum = maxSumRec(a, center+1, right);
		//计算中心最大(左边)
		int maxCenterSum_left=0;
		int leftTemp=0;
		for(int i=center ; i>=left; i-- ) {
			leftTemp+=a[i];
			if(leftTemp>maxCenterSum_left) {
				maxCenterSum_left=leftTemp;
			}
		}
		//计算中心最大(右边)
		int maxCenterSum_right=0;
		int rightTemp=0;
		for(int i=center+1; i<=right ; i++) {
			rightTemp+=a[i] ; 
			if(rightTemp>maxCenterSum_right) {
				maxCenterSum_right=rightTemp;
			}
		}
		//计算中心最大(左边+右边)
		int maxCenterSum=maxCenterSum_left+maxCenterSum_right;
		//三个范围的最大取最大
		return Integer.max(maxRightSum, Integer.max(maxLeftSum, maxCenterSum));
	}
}
	
/* * 递归编写心得： * 1. 先写Base Case * 2. 把需要的下一级结果看成已知结果调用。 */

算法三：完美的线性算法（山峰算法，我的命名）

分析

代码

/** * 第四种算法，线性的复杂度！！ * 把数组分成“自然”的多段，段的开始大于0，段的结尾是段的子序列和最大值 * Linear-time maximum contiguous subsequence sum algorithm. * @param a * @return */
	public static int leftIndex = 0 ;
	public static int leftIndex_temp=0;
	public static int rightIndex = 0 ;
	public static int maxSubSum4(int[] a ) {
		int maxSum=0;
		
		int maxSum_temp=0;
		for(int i=0 ;i<a.length ; i++) {
			maxSum_temp+=a[i];
			if(maxSum_temp<0) {
				maxSum_temp=0; // 这一段小于0，这一段就中断了。把起点初始化
				leftIndex_temp = i+1;
			}else if(maxSum_temp>maxSum) { //刷新高峰时候，记录
				maxSum= maxSum_temp;
				rightIndex = i;
				leftIndex=leftIndex_temp;
			}
		}
		return maxSum;
	}