小松的技术博客

六和敬

若今生迷局深陷,射影含沙。便许你来世袖手天下,一幕繁华。 你可愿转身落座,掌间朱砂,共我温酒煮茶。

一道递归算法题

双11来了!!此时此刻,丑的人在挥霍钱财去掩饰自己,帅的人则提笔写作点缀这个世界。

今天一位师弟问了我一道递归算法题,他写出了demo,但是找不到错误在哪里,我发现师弟对采用递归的思路不时非常清晰,所以写出的代码略显混乱,因此很不好debug。所以今天我也花了点时间整理了下思路,并写出了demo,希望能帮到师弟,顺便把代码与思路分享出来(采用的时js语言)。

问题:

已知一个number类型的数组,然后我们要从这个数组中得到一个“连续的”且“和最大”的子数组。

思路分析:

解决方法还是会有很多的,这里主要是二分法递归的解决方案。

对于这个数组,从我们想要的数组出现的位置,可以把数组划分为三个区域:数组的前半段,数组的后半段,数组的前半段的最后一个元素与数组的后半段第一个元素连接的中间段:

  • 前半段:前半段又可以当成一个完整的数组,那么又可以继续划分三个区域,这就是可以递归的原因
  • 后半段:同前半段逻辑
  • 中间段:中间端已经确定了两个元素(前半段的最后一个元素与后半段第一个元素),那么就可以向两侧进行逐个相加取最大值的方式获得“和最大”的子数组

当获得三段分别得最大子数组和最大和之后,进行比较就可以得到我们想要的结果了。简单分析后,其思路会比想象中简单吧。

代码实现

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 [];
}

下面是测试代码:

 var testArr = [-1,-2,2,3,4];
 console.log(getMaxSumChildArr(testArr));//[2, 3, 4]

var testArr1 = [-1,-2,2,-1,-5,3,4,8,6,-3,5,-3];
console.log(getMaxSumChildArr(testArr1));//[3, 4, 8, 6, -3, 5]

其实递归只要动手前把思路整理通顺,实现起来还是比较容易的。

←支付宝← →微信 →
comments powered by Disqus