（一）最大子列和的逐步优化 JS实现

最大子列和
//1，算法一，去穷举 O(n^3)

function maxSubSquSum1 (arr) {
    var sum = 0,MaxSum = 0;
    var ans = [];
    for(var s=0;s<arr.length;s++){//枚举开始位置      
        for(var e=s;e<arr.length;e++){//枚举开始位置
            sum = 0;
            for(var i=s;i<=e;i++){//计算开始到结束的位置
                sum+=arr[i];
            }
            if(sum>MaxSum){
                MaxSum = sum;
                ans = arr.slice(s,e+1);
            }
        }
    }
    return ans;
}

2.算法二，穷举优化O(n^2)，穷举第三层可以省略，因为都是之前的和加上当前的尾

function maxSubSquSum2 (arr) {
    var sum = 0,MaxSum = 0;
    var ans = [];
    for(var s=0;s<arr.length;s++){//枚举开始位置
        sum = 0;        //***注意移位置
        for(var e=s;e<arr.length;e++){//枚举开始位置
            sum+=arr[e];
            if(sum>MaxSum){
                MaxSum = sum;
                ans = arr.slice(s,e+1);
            }
        }
    }
    return ans;
}

3.算法三，分而治之的方法，O(nlogn),每次切切半求两边的最大子列和，而后判断中间可不可以合并

function maxSubSquSum3 (arr) {
    var ans = [];
    maxSubSeq(0,arr.length-1);
    return arr.slice(ans[0],ans[1]+1);

    function maxSubSeq (subs,sube) {//传递半边数组的起止位置
        ans = [];
        if(subs==sube){//递归边界
            if(arr[subs]>0){
                ans[0]=subs;//起始位置
                ans[1]=sube;//结束为止
                ans[2]=arr[subs];//和
            }
            return ans;         
        }
        var mid = parseInt((subs+sube)/2);
        var ansleft = maxSubSeq(subs,mid);//第一种情况，出现在左边
        var ansright = maxSubSeq(mid+1,sube);//第二种情况，出现在右边
        
        var ansmid = [];//第三种情况，从中间延伸
        var leftbordersum=0,Maxleftbordersum=0,left=mid,right=mid;
        for(var i=mid;i>=subs;i--){
            leftbordersum+=arr[i];
            if(leftbordersum>Maxleftbordersum){
                Maxleftbordersum = leftbordersum;
                ansmid[0] = i;
            }
        }
        var rightbordersum=0,Maxrightbordersum=0;
        for(i=mid+1;i<=sube;i++){
            rightbordersum+=arr[i];
            if(rightbordersum>Maxrightbordersum){
                Maxrightbordersum = rightbordersum;
                ansmid[1] = i;
            }
        }
        ansmid[2] = Maxleftbordersum+Maxrightbordersum;
        
        if(ansleft.length==0||ansright.length==0){
            return ansleft.concat(ansright);
        }
        if(ansmid[2]>=ansleft[2]&&ansmid[2]>ansright[2]){
            ans = ansmid;
        }
        else if(ansleft[2]>ansright[2]){
            ans = ansleft;
        }else{
            ans = ansright;
        }
        return ans;
    }   
}

4.算法四，在线算法，O(n),若前面的和小于0则抛弃前面的重新计算

function maxSubSquSum4 (arr) {
    var sum= 0,maxsum = 0;
    var left=0,right=0;
    for(var i=0;i<arr.length;i++){
        sum+=arr[i];
        if(sum>maxsum){
            maxsum = sum;
            right = i;
        }else if(sum<0){//小于0则抛弃前面的重新计算
            sum = 0;
            left = i+1;
        }
    }
    if(left<=right){
        return arr.slice(left,right+1);
    }
}

maxSubSquSum1([-2, 1, -3, 4, -1, 2, 1, -5, 4]);