读书笔记——最大子序列和问题

以下代码主要来自于《数据结构与算法分析 Java语言描述》第二章，增加了一些打印的log。

public class MaxSubSumTest { public static void main(String[] args) { int[] testArray = new int[]{-2, 11, -4, 13, -5, -2}; System.out.println("maxSubSum1: " + maxSubSum1(testArray)); System.out.println("maxSubSum2: " + maxSubSum2(testArray)); System.out.println("maxSubSum3: " + maxSubSum3(testArray)); System.out.println("maxSubSum4: " + maxSubSum4(testArray)); } public static int maxSubSum1(int[] a) { System.out.println("------maxSubSum1--------"); long startTime = System.currentTimeMillis(); int maxSum = 0; for (int i = 0; i < a.length; i++) { for (int j = i; j < a.length; j++) { int thisSum = 0; for (int k = i; k <= j; k++) { thisSum += a[k]; System.out.print(" a[" + k + "] "); } System.out.println("-->" + thisSum); if (thisSum > maxSum) { maxSum = thisSum; } } } long endTime = System.currentTimeMillis(); System.out.println(startTime + "--->" + endTime); System.out.println("------maxSubSum1 return--------"); System.out.println("------" + (endTime - startTime) + " millis--------"); return maxSum; } public static int maxSubSum2(int[] a) { System.out.println("------maxSubSum2--------"); long startTime = System.currentTimeMillis(); int maxSum = 0; for (int i = 0; i < a.length; i++) { int thisSum = 0; for (int j = i; j < a.length; j++) { thisSum += a[j]; System.out.print(" a[" + i + "-" + j + "] "); System.out.println("-->" + thisSum); if (thisSum > maxSum) { maxSum = thisSum; } } } long endTime = System.currentTimeMillis(); System.out.println(startTime + "--->" + endTime); System.out.println("------maxSubSum2 return--------"); System.out.println("------" + (endTime - startTime) + " millis--------"); return maxSum; } public static int maxSubSum3(int[] a) { return maxSumRec(a, 0, a.length - 1); } private static int maxSumRec(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 = maxSumRec(a, left, center); int maxRightSum = maxSumRec(a, center + 1, right); int maxLeftBorderSum = 0; int leftBorderSum = 0; for (int i = center; i >= left; i--) { leftBorderSum += a[i]; if (leftBorderSum > maxLeftBorderSum) { maxLeftBorderSum = leftBorderSum; } } int maxRightBorderSum = 0; int rightBorderSum = 0; for (int i = center + 1; i <= right; i++) { rightBorderSum += a[i]; if (rightBorderSum > maxRightBorderSum) { maxRightBorderSum = rightBorderSum; } } System.out.println("left: " + left + ", right: " + right); System.out.println("maxleft: " + maxLeftBorderSum + ", maxright: " + maxRightSum + ", " + "maxLeftBorderSum: " + maxLeftBorderSum + " maxRightBorderSum: " + maxRightBorderSum); return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum); } private static int max3(int a, int b, int c) { return Math.max(Math.max(a, b), c); } public static int maxSubSum4(int[] a) { int maxSum = 0; int thisSum = 0; for (int j = 0; j < a.length; j++) { thisSum += a[j]; if (thisSum > maxSum) { maxSum = thisSum; } else if (thisSum < 0) { thisSum = 0; } } return maxSum; } } 运行结果为

------maxSubSum1-------- a[0] -->-2 a[0] a[1] -->9 a[0] a[1] a[2] -->5 a[0] a[1] a[2] a[3] -->18 a[0] a[1] a[2] a[3] a[4] -->13 a[0] a[1] a[2] a[3] a[4] a[5] -->11 a[1] -->11 a[1] a[2] -->7 a[1] a[2] a[3] -->20 a[1] a[2] a[3] a[4] -->15 a[1] a[2] a[3] a[4] a[5] -->13 a[2] -->-4 a[2] a[3] -->9 a[2] a[3] a[4] -->4 a[2] a[3] a[4] a[5] -->2 a[3] -->13 a[3] a[4] -->8 a[3] a[4] a[5] -->6 a[4] -->-5 a[4] a[5] -->-7 a[5] -->-2 1489143623437--->1489143623437 ------maxSubSum1 return-------- ------0 millis-------- maxSubSum1: 20 ------maxSubSum2-------- a[0-0] -->-2 a[0-1] -->9 a[0-2] -->5 a[0-3] -->18 a[0-4] -->13 a[0-5] -->11 a[1-1] -->11 a[1-2] -->7 a[1-3] -->20 a[1-4] -->15 a[1-5] -->13 a[2-2] -->-4 a[2-3] -->9 a[2-4] -->4 a[2-5] -->2 a[3-3] -->13 a[3-4] -->8 a[3-5] -->6 a[4-4] -->-5 a[4-5] -->-7 a[5-5] -->-2 1489143623437--->1489143623437 ------maxSubSum2 return-------- ------0 millis-------- maxSubSum2: 20 left: 0, right: 1 maxleft: 0, maxright: 11, maxLeftBorderSum: 0 maxRightBorderSum: 11 left: 0, right: 2 maxleft: 11, maxright: 0, maxLeftBorderSum: 11 maxRightBorderSum: 0 left: 3, right: 4 maxleft: 13, maxright: 0, maxLeftBorderSum: 13 maxRightBorderSum: 0 left: 3, right: 5 maxleft: 8, maxright: 0, maxLeftBorderSum: 8 maxRightBorderSum: 0 left: 0, right: 5 maxleft: 7, maxright: 13, maxLeftBorderSum: 7 maxRightBorderSum: 13 maxSubSum3: 20 maxSubSum4: 20

方法4引入了联机算法（on-line algorithm）的概念。主要特点是不需要被记忆，只顺序读入就能给出子序列问题正确答案。