package Chapter1;
public
class MaxSubSum
{
/**
* Cubic maximun contiguous susequence sum algorithm.
*/ public static int MaxSubSum1(int[] a) { 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]; if (thisSum > maxSum) maxSum = thisSum; } } return maxSum; } /** * Quadratic maximum contiguous subsequence sum algorithm. */ public static int maxSubSum2(int[] a) { 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]; if (thisSum > maxSum) maxSum = thisSum; } } return maxSum; } /** * Resursive maximum contiguous subsequence sum algorithm. Finds maximum sum * in subarray spanning a[left
right]. Does not attempt to maintain actual * est sequence. */ private 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 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++) { leftBorderSum += a[i]; if (rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum); } /** * Return the max of the three number. * * @param a * the first number. * @param b * the second number. * @param c * the thrid number. * @return the max of the three number. */ private static int max3(int a, int b, int c) { if (a > b) { if (a > c) return a; else return c; } else { if (b > c) return b; else return c; } } /** * Driver for divide-and-conquer maximum contiguous subsequence sum * algorithm */ public static int maxSubSum3(int[] a) { return maxSumRec(a, 0, a.length - 1); } /** * Linear-time maximum contiguous subsequence sum algorithm. */ public static int maxSubSum4(int[] a) { int maxSum = 0, 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; }
}
本文转自冬冬博客园博客，原文链接：http://www.cnblogs.com/yuandong/archive/2006/08/17/479690.html
，如需转载请自行联系原作者
