最大子序列和的四种算法

1.穷举法

算法思想：算出每个子序列的和，即算出序列中第i个到第j个数的和(j>=i)，并进行比较

算法：

	public static int maxSubSum1(int[] a) {
		int maxSum = 0;
		int sum;
		for (int i = 0; i < a.length; i++) {
			for (int j = i; j < a.length; j++) {
				sum = 0;
				for (int k = i; k <= j; k++) {
					sum += a[k];// 计算a[i]到a[j]的和
				}
				if (sum > maxSum) {
					maxSum = sum;
				}
			}
		}
		return maxSum;
	}

运行时间为O(N^3)

2.对上述第一个算法的改进

算法思想：第一个算法的第三个for循环中有大量不必要的重复计算，如：计算i到j的和，然而i到j-1的和在前一次的循环中已经计算过，无需重复计算，故该for循环可以去掉

算法：

	public static int maxSubSum2(int[] a) {
		int maxSum = 0;
		int sum;
		for (int i = 0; i < a.length; i++) {
			sum = 0;
			for (int j = i; j < a.length; j++) {
				sum += a[j];
				if (sum > maxSum) {
					maxSum = sum;
				}
			}
		}
		return maxSum;
	}

运行时间为O(N^2)

3.分而治之

算法思想：把问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”的部分。“治”阶段将两个子问题的解修补到一起并可能再做些少量的附加工作，最后得到整个问题的解。

在该问题中，如果把序列从中间分为两部分，那么最大子序列和可能在三处出现，要么整个出现在输入数据的左半部，要么整个出现在右半部，要么跨越分界线。前两种情况可以递归求解，第三种情况的最大和可以通过求出前半部分（包括前半部分的最后一个元素）的最大和以及后半部分（包含后半部分的第一个元素）的最大和而得到，此时将两个和相加。

算法：

	// 参数：处理数组，左边界，右边界
	public static int maxSubSum3(int[] a, int left, int right) {
		if (left == right) {
			if (a[left] > 0) {
				return a[left];
			} else {
				return 0;
			}
		}

		int center = (left + right) / 2;
		int maxLeftSum = maxSubSum3(a, left, center);
		int maxRightSum = maxSubSum3(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;
			}
		}

		int maxBorderSum = maxLeftBorderSum + maxRightBorderSum;
		return maxBorderSum > maxLeftSum ? maxBorderSum > maxRightSum ? maxBorderSum : maxRightSum
				: maxLeftSum > maxRightSum ? maxLeftSum : maxRightSum;
	}

运行时间O(N*logN)

4.最优起点

算法思想：设a[i]为和最大序列的起点，则如果a[i]是负的，那么它不可能代表最优序列的起点，因为任何包含a[i]作为起点的子序列都可以通过a[i+1]作起点而得到改进。

类似的，任何负的子序列也不可能是最优子序列的前缀。

算法：

	public static int maxSubSum4(int[] a){
		int maxSum=0,sum=0;
		for(int i=0;i<a.length;i++){
			sum+=a[i];
			if(sum>maxSum){
				maxSum=sum;
			}else if(sum<0){
				sum=0;
			}
		}
		return 0;
	}

运行时间：O(N)