最大连续子列和问题

给出一个数组求最大的连续子列和
方案1:穷举

    public int findMax(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0 ; i < nums.length; i++){
            int thisSum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                thisSum = thisSum + nums[j];
                if(thisSum > maxSum){
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

双重for循环，时间复杂度无疑是O(n^2)

方案2:分而治之

    private int findSubMaxSum(int[] nums, int start, int end){
        if(start == end){
            return nums[start] < 0 ? 0 : nums[start];
        }
        int center = (start + end) / 2;
        //左边部分最大连续子列和
        int leftMax = findSubMaxSum(nums, start, center);

        //右边部分最大连续子列和
        int rightMax = findSubMaxSum(nums, center + 1, end);

        //跨中点最大连续子列和--从中间向左边扫描
        int center2LeftMax = Integer.MIN_VALUE; int center2LeftSum = 0;
        for(int i = center; i >= start; i--){
            center2LeftSum += nums[i];
            center2LeftMax = Math.max(center2LeftMax, center2LeftSum);
        }

        //跨中点最大连续子列和--从中间向右边扫描
        int center2RightMax = Integer.MIN_VALUE; int center2RightSum = 0;
        for(int i = center + 1; i <= end; i++){
            center2RightSum += nums[i];
            center2RightMax = Math.max(center2RightMax, center2RightSum);
        }

        //返回结果 Max(左边部分最大连续子列和, 右边部分最大连续子列和, 跨中点最大连续子列和=(从中间向左边扫描 + 从中间向右边扫描))
        return Math.max(Math.max(leftMax, rightMax), center2RightMax + center2LeftMax);
    }

时间复杂度O(nlgn)，推导过程如下
假设求长度为N的数组的最大连续子列和的时间复杂度为T(N),那么
T(N) = 2T(N/2) + cN
T(N/2) = 左半部分最大连续子列和的时间复杂度 = 右半部分最大连续子列和的时间复杂度
c * N = 跨中点最大连续子列和时间复杂度
继续推导可得
T(N) = 2(2T(N/2^2) + cN/2) + cN = 2^kO(1) + ckN
由算法可知当规模=1时退出递归，则有
N/2^k = 1 --> k = lgN --> T(N) = N + NlgN --> O(n) = O(n*lgn)

方案3:在线处理

    private int findSubMaxSum(int[] nums){
        int maxSum = Integer.MIN_VALUE; int thisSum = 0;
        for(int i = 0 ; i < nums.length; i++){
            thisSum += nums[i];
            thisSum = thisSum < 0 ? 0 : thisSum;
            maxSum = Math.max(thisSum, maxSum);
        }
        return maxSum;
    }

if(sum(0, n-1) >=0) --> sum(0, n) >= sum(0, n-1)
if(sum(0, n-1) < 0) --> sum(0, n) < num[n] --> 这个时候只需要从num[n]作为起点开始求连续子列和即可
该算法复时间复杂度为O(n)