递归法解决LIS问题，对源码的一个疑问

Question

// var arr = [ 4, 10, 4, 3, 8, 9 ];

var arr = [ 10, 9, 2, 5, 3, 7, 101, 18 ];

// 为了求得数组的LIS，我认为只要直接调用 getMaxLength(arr, arr.length-1)就行了

alert( getMaxLength( arr, arr.length - 1 ) );

/**   看了老师的源代码，

int res = 1;

for( int i = 0 ; i < nums.size() ; i ++ )

    res = max(res, getMaxLength(nums, i));

=====================================

我认为这个循环就是一个健壮性，但不需要这个循环，直接   getMaxLength(arr, arr.length-1) 就够了，

请问下老师，是不是 >_<

*/

function getMaxLength( nums, index ){

   

var res = 1;

for( var i = 0; i < index; i ++ ){

   if( nums[index] > nums[i] ){

    res = Math.max( res, 1 + getMaxLength( nums, i  ) );

   }

}

return res;

}

Answer 1

liuyubobobo 2017-04-10 11:38:20

我没有特别理解你的问题。在我这里的源代码：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/09-Dynamic-Programming/Course%20Code%20(C%2B%2B)/08-Longest-Increasing-Subsequence/main2.cpp

你的意思是哪个循环不需要？

Answer 2

提问者 甲骨文_0001 2017-04-10 11:44:32

就是这份源码，上面的 lenghtOfLIS函数里 就有 循环 nums数组，然后依次比较，最后取得最大值，我的提问源于这份代码，

刚刚看到了 波波老师 gitub上的代码，我的疑虑消解了>_<

• liuyubobobo #1

  明白了，你的问题在于使用递归+记忆化搜索的代码。对应我的github上这份代码：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/09-Dynamic-Programming/Course%20Code%20(C%2B%2B)/08-Longest-Increasing-Subsequence/main.cpp
  
  嗯，那个循环是需要的哦：）