查找一串子列中最大子序列

穷举法

public static int maxSubSum1(int[] array) {
    int maxSum = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j < array.length; j++) {
            int thisSum = 0;
            for (int k = i; k < j; k++) {
                thisSum += array[k];
            }
            if (thisSum > maxSum) {
                maxSum = thisSum;
            }
        }
    }
    return maxSum;
}

时间复杂度O(n^3)

穷举法改进

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

时间复杂度O(n^2)

分治法

    public static int maxSubSum3(int[] array, int left, int right) {
        // 基准
        if (right - left == 1) {
            if (array[left] > 0) {
                return array[left];
            }
            return 0;
        }
        int centre = (left + right) / 2;
        int maxLeftSum = maxSubSum3(array, left, centre);
        int maxRightSum = maxSubSum3(array, centre, right);

        int maxLeftBorderSum = 0, leftBorderSum = 0;
        for (int i = centre - 1; i >= left; i--) {
            leftBorderSum += array[i];
            if (leftBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum = leftBorderSum;
            }
        }

        int maxRightBorderSum = 0, rightBorderSum = 0;
        for (int j = centre; j < right; j++) {
            rightBorderSum += array[j];
            if (rightBorderSum > maxRightBorderSum) {
                maxRightBorderSum = rightBorderSum;
            }
        }
        int maxBorderSum = maxLeftBorderSum + maxRightBorderSum;
        return maxLeftSum > maxRightSum ? (maxLeftSum > maxBorderSum ? maxLeftSum : maxBorderSum)
                : (maxRightSum > maxBorderSum ? maxRightSum : maxBorderSum);
    }

时间复杂读O(nlog(n))

一种巧妙的方法

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

时间复杂度O(n)

简要说明正确性

子列的起始和结束必须是一个正数，负数在子列中间当且仅当thisSum>0时才有意义，否则长度为0的子列也比这个子列大。