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

来源：9-8 LIS问题 Longest Increasing Subsequence

甲骨文_0001

2017-04-10

// 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;

}

写回答

2回答

liuyubobobo

2017-04-10

我没有特别理解你的问题。在我这里的源代码：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

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

甲骨文_0001

提问者

2017-04-10

//szimg.mukewang.com/58eaff060001225205470539.jpg

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

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

liuyubobobo

明白了，你的问题在于使用递归+记忆化搜索的代码。对应我的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 嗯，那个循环是需要的哦：）

2017-04-11

共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

查看课程

相似问题

lc203 递归写法复杂度分析

回答 1

关于视频中归并排序的递归时间复杂度分析的一点疑问

回答 2

lc160 怎样用递归写法呢？

回答 2

Leetcode 779求解第N-1行中第K-1个字符疑问

回答 1

请问如何避免系统爆栈

回答 1

打开慕课网App查看更多内容