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 thisSum = 0;
thisSum += a[j];
* 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++) {
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;
return c;
} else {
if (b > c)
return b;
* 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;
}
时间复杂度分别是：O(N3),O(N2),O(NlogN),O(N).
本文转自冬冬博客园博客，原文链接：http://www.cnblogs.com/yuandong/archive/2006/08/17/479690.html，如需转载请自行联系原作者