问题

给定N个整数序列

求函数

的最大值。

算法一

算出所有可能的连续子列的和，并比较

public int MaximumSubsequenceSum1(int[] array,int size) {
    int maxSum=0;
    int tempSum=0;
    for(int i=0;i<size;i++) {
        for(int j=i;j<size;j++) {
            for(int k=i;k<=j;k++) {
                tempSum+=array[k];
            }
            if(tempSum>maxSum) {
                maxSum=tempSum;
            }
        }
    }
    return maxSum;
}

时间复杂度O（N^3）

算法二

在解法一的基础上进行改进

public static int MaximumSubsequenceSum2(int[] array,int size) {
    int maxSum=0;
    int tempSum=0;
    for(int i=0;i<size;i++) {
        tempSum=0;
        for(int j=i;j<size;j++) {
            tempSum+=array[j];
            if(tempSum>maxSum) {
                maxSum=tempSum;
            }
        }
    }
    return maxSum;
}

时间复杂度O（N^2）

算法三

递归计算：将数组分为两部分，分别计算左、右和包含左右两边元素的三个最大子列和。

public static int MaximumSubsequenceSum3(int[] array,int size) {
    return MaximumSubsequenceSum3Recursion(array,0,size-1);
}
public static int MaximumSubsequenceSum3Recursion(int[] array,int leftIndex,int rightIndex) {
    int maxLeftSum;
    int maxRightSum;
    int maxLeftBorderSum;
    int maxRightBorderSum;
    int tempLeftBorderSum;
    int tempRightBorderSum;
    int centerIndex;
    //传入数组只有一个数时终止
    if(leftIndex==rightIndex) {
        return (array[leftIndex]>=0)? array[leftIndex]:0;
    }
    //分
    centerIndex=(leftIndex+rightIndex)/2;
    maxLeftSum=MaximumSubsequenceSum3Recursion(array,leftIndex,centerIndex);
    maxRightSum=MaximumSubsequenceSum3Recursion(array, centerIndex+1, rightIndex);
    //子列元素在左右两边存在的情况
    maxLeftBorderSum=0;
    tempLeftBorderSum=0;
    for(int i=centerIndex;i>=leftIndex;i--) {
        tempLeftBorderSum+=array[i];
        if(tempLeftBorderSum>maxLeftBorderSum) {
            maxLeftBorderSum=tempLeftBorderSum;
        }
    }
    maxRightBorderSum=0;
    tempRightBorderSum=0;
    for(int i=centerIndex;i<=leftIndex;i++) {
        tempRightBorderSum+=array[i];
        if(tempRightBorderSum>maxRightBorderSum) {
            maxRightBorderSum=tempRightBorderSum;
        }
    }
    return Math.max(maxLeftSum, Math.max(maxRightSum, maxLeftBorderSum+maxRightBorderSum));
}

时间复杂度O（NlogN）。由于是递归计算，所以空间复杂度较大

算法四（在线处理）

public static int MaximumSubsequenceSum3(int[] array,int size) {
    int maxSum=0;
    int tempSum=0;
    for(int i=0;i<size;i++) {
        tempSum+=array[i];
        if(tempSum>maxSum) {
            maxSum=tempSum;
        }else if(tempSum<0) {
            tempSum=0;
        }
    }
    return maxSum;
}

时间复杂度O（N）