phpstudy集成环境

 首页 > JS 求数组中 和最大的连续子串？

JS 求数组中 和最大的连续子串？

input:数组 类似于 [-2, 1, -3, 4, -1, 2, 1, -5, 4]
output： 6: [4, -1, 2, 1]
如何做啊？

//通过每次与前一位的最大连续子串的信息做比较进行拼接
function getTempByPrevSeq(PrevTemp, currentValue) {
    //这里规定，0也可以进行子串拼接
    if (PrevTemp.sum >= 0) {
        return {
            num: PrevTemp.num + 1,
            sum: PrevTemp.sum + currentValue
        };
    } else {
        return {
            num: 1,
            sum: currentValue
        }
    }
}

function getMaxSumSeqArr(input) {
    if (input.length === 0) return;
    var temps = []; // 存储每一位与前面连续之后可得最大值的信息，以便后面的每一位进行迭代更新

    //第一位向前的最大子串就是它自己本身
    var temp = {
        num: 1,
        sum: input[0]
    };
    temps.push(temp);

    for (var i = 1, len = input.length; i < len; i++) {
        var ref = input[i];
        //从前向后迭代
        var temp = getTempByPrevSeq(temps[i-1], ref);
        temps.push(temp);
    }

    //存储了迭代过程中的信息, 可以在这里看看
    console.log(temps);

    var maxValue, //获取最大值
        indexArr = []; //获取多个结果的index

    maxValue = temps[0].sum;
    indexArr.push(0);

    for (var i = 1, len = temps.length; i < len; i++) {
        var ref = temps[i];
        if (ref.sum === maxValue) {
            indexArr.push(i);
        } else if (ref.sum > maxValue) {
            maxValue = ref.sum;
            indexArr.length = 0; //重置数组
            indexArr.push(i);
        }
    }

    //output
    console.log("MaxValue: " + maxValue);
    for (var i = 0, len = indexArr.length; i < len; i++) {
        var index     = indexArr[i],
            ref     = temps[index];
        console.log(input.slice(index-ref.num+1, index+1));
    }

}

var input = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
getMaxSumSeqArr(input);

该算法效率为o(n)。
对于每一位数，先取出前一位的信息进行判断前面连续子串的总和，如果总和大于等于0，则将自己与前面进行拼接，否则只保留自身，以此生成处理信息传递给下一位处理。

写错了，再研究一下怎么写。

    我的思路很简单，就是把复杂的问题分成几步来完成：
    
    1.把数组按照规定的长度切割成不同的子串，返回一个二维数组 
    2.获得二维数组中和最大的数组和最大的和（返回一个对象） 
    3.处理输入和格式化输出结果。
    
    /* 求数组中 和最大的 连续子串 */
    
    // 把数组按照规定的长度切割成不同的子串 
    function subArr(_arr, _length) {
        let newArr = [],len = _arr.length;
        for (let i = 0; i < len; i++){
            let res = []
            for (let j = i; j < i + _length; j++) {
                res.push(_arr[j])
            }
            if (res.length === _length) { 
                newArr.push(res)
            }
        }
        return newArr;
    }

    // 获得二维数组中和最大的数组 
    function getMostArr(arr) {
        let most = 0, sum = 0;
        arr.forEach((item,i) => {
            let _sum = 0;
            item.forEach(sub => _sum+=sub)
            if (_sum > sum) {
                sum = _sum,
                most = i
            }
        })
        return { arr: arr[most], sum: sum }
    }

    function getSubArr(_arr) {
        let source = []
        for (let i = 1; i <= _arr.length; i++) {
            let arr = subArr(_arr, i);
            source = source.concat(arr)
        }
        let most = getMostArr(source);
        return most.sum + ": [" + most.arr + ']'
    }

    console.log(getSubArr([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  // 输出 6: [4, -1, 2, 1]

最大子序列问题。http://blog.cgsdream.org/2015/11/10/recursion-algorithm-analysis/

function getMaxSumChildArr(arr){
    //确保输入是数组
    if(Array.isArray(arr) || Object.prototype.toString.call(arr) === "[object Array]"){
        var length = arr.length;
        if(length===1){
          return arr;
        }

        var slice = Array.prototype.slice;
        //start,end采用的时左闭又开得模式，即[start,end),这比较符合程序员思维
        function getMaxArr(arr,start,end){
          if(end-start==1){//如果只有一个元素，递归终止条件
            var output = {
              arr:[arr[start]],
              sum:arr[start]
            };
            return output;
          }
          var leftOutput, rightOutput, centerOutput;
          var center =  Math.floor((start + end)/2);

          //前半段处理（递归）
          var leftOutput =  getMaxArr(arr,start,center);

          //后半段处理（递归）
          var rightOutput = getMaxArr(arr,center,end);

          //中间段
          var centerMaxSum,
              tmpSum=0,
              tmpMax = -Infinity,
              centerIndexLeft,
              centerIndexRight;
          //从前半段最后一个元素向前，逐个相加获取“和最大”的值以及最小数组下标
          for(var i=center-1;i>=0;i--){
            tmpSum+= arr[i]
            if(tmpSum>=tmpMax){
              tmpMax = tmpSum;
              centerIndexLeft = i;
            }
          }
          //保存上一步的最大值并清空临时变量
          centerMaxSum = tmpMax;
          tmpSum=0;
          tmpMax = -Infinity;
          //从后半段第一个元素向后，逐个相加获取“和最大”的值以及最大数组下标
          for(var i=center;i<length;i++){
            tmpSum+= arr[i]
            if(tmpSum>=tmpMax){
              tmpMax = tmpSum;
              centerIndexRight = i;
            }
          }
          centerMaxSum += tmpMax;
          centerOutput = {
            arr: slice.call(arr,centerIndexLeft,centerIndexRight+1),
            sum:centerMaxSum
          }

          //对三段做比较
          var output = leftOutput.sum > rightOutput.sum ? leftOutput : rightOutput;
          output = output.sum >centerOutput.sum ? output : centerOutput;
          return output;
        }
        var output = getMaxArr(arr,0,length);
        return output.arr;
    }
    return [];
}
【热门文章】
【热门文章】