f*******r
发帖数: 1086 | 1 自己刚刚写了一下O(n^2)的算法，还没想明白
O(nlogk)的算法的思想，哪位大侠麻烦赐教一下，
非常感谢！ |
l*****a
发帖数: 14598 | 2 where does K come from?
【在 f*******r 的大作中提到】
: 自己刚刚写了一下O(n^2)的算法，还没想明白
: O(nlogk)的算法的思想，哪位大侠麻烦赐教一下，
: 非常感谢！
|
f*******r
发帖数: 1086 | 3 也可以说是nLog(n) 吧，我是看到有文章提到k表示子序列的长度
【在 l*****a 的大作中提到】
: where does K come from?
|
S******a
发帖数: 862 | 4 http://en.wikipedia.org/wiki/Longest_increasing_subsequence
【在 f*******r 的大作中提到】
: 自己刚刚写了一下O(n^2)的算法，还没想明白
: O(nlogk)的算法的思想，哪位大侠麻烦赐教一下，
: 非常感谢！
|
f*******r
发帖数: 1086 | 5 非常感谢，不过刚看了一下还是没有清晰的思路，
能简单地描述一下思想吗？谢谢了！
【在 S******a 的大作中提到】
: http://en.wikipedia.org/wiki/Longest_increasing_subsequence
|
b******v
发帖数: 1493 | 6 wikipedia上面有
【在 f*******r 的大作中提到】
: 自己刚刚写了一下O(n^2)的算法，还没想明白
: O(nlogk)的算法的思想，哪位大侠麻烦赐教一下，
: 非常感谢！
|
c*********7
发帖数: 19373 | 7 也提出个问题，如果每次都是从上次结束的位置开始岂不是到O(n).比如第一个
increasing 是从1到k1,然后下个搜索从k1+1开始。 |
l******o
发帖数: 144 | 8 如果wiki都不能让你理解的话，我们可能也很难了。
非常感谢，不过刚看了一下还是没有清晰的思路，
能简单地描述一下思想吗？谢谢了！
【在 f*******r 的大作中提到】
: 非常感谢，不过刚看了一下还是没有清晰的思路，
: 能简单地描述一下思想吗？谢谢了！
|
x****r
发帖数: 99 | 9 wiki里面那个还稍微麻烦了，他那样是可以retrieve这个sequence的方法，如果只需要
长度，可以这样做
数组a[i]里面可以存长度为i的子序列，最小的结尾是多少
基本是这样
数组： 99 100 100 1 2 3 4
第1步. 99 ：binary search 最大一个<=99的，没有，所以a[1] = 99;
第2步. 100 ：binary search 最大一个<=100的，就是a[1]， 所以a[2] = 100;（意
思是现在长度为2的不减数列最少是100结尾）
第3步. 100 ：binary search 最大一个<=100的，是a[2]，所以a[3] = 100;
第4步. 1 : binary search 最大一个<=1的，没有，所以a[1] = 1;
第5步. 2 : binary search 最大一个<=2的，是a[1],所以A[2] = 2；
第6步. 同上，设置a[3] = 3;
第7步. 同上, 设置a[4] = 4;
至此，取得最大的a的index，就是4，所以长度最长的不减小子串是4，不知道讲明白了
没有 |
y**i
发帖数: 1112 | 10 你这个情况如果数组是99 100 100 1 2呢，最后不是到a[2] = 2就停止了，最大index
= 2了？
【在 x****r 的大作中提到】
: wiki里面那个还稍微麻烦了，他那样是可以retrieve这个sequence的方法，如果只需要
: 长度，可以这样做
: 数组a[i]里面可以存长度为i的子序列，最小的结尾是多少
: 基本是这样
: 数组： 99 100 100 1 2 3 4
: 第1步. 99 ：binary search 最大一个<=99的，没有，所以a[1] = 99;
: 第2步. 100 ：binary search 最大一个<=100的，就是a[1]， 所以a[2] = 100;（意
: 思是现在长度为2的不减数列最少是100结尾）
: 第3步. 100 ：binary search 最大一个<=100的，是a[2]，所以a[3] = 100;
: 第4步. 1 : binary search 最大一个<=1的，没有，所以a[1] = 1;
|
x****r
发帖数: 99 | 11 不是的，因为看到第三个100的时候，最大length已经被设置为3了，所以最后还是返回
3，返回的值是
这个数组里index最大的一个非空的值
index
【在 y**i 的大作中提到】
: 你这个情况如果数组是99 100 100 1 2呢，最后不是到a[2] = 2就停止了，最大index
: = 2了？
|
K******g
发帖数: 1870 | 12 不懂。
首先，binary search整个数组吗？比如说“binary search 最大一个<=99的”， 为什
么“没有”，如果是搜索这个数组，难道99不是吗？如果是搜索剩余的数组，难道4不
是吗？
为什么到第4步的时候，就回到“a【1】”去了？
非常confusing
【在 x****r 的大作中提到】
: wiki里面那个还稍微麻烦了，他那样是可以retrieve这个sequence的方法，如果只需要
: 长度，可以这样做
: 数组a[i]里面可以存长度为i的子序列，最小的结尾是多少
: 基本是这样
: 数组： 99 100 100 1 2 3 4
: 第1步. 99 ：binary search 最大一个<=99的，没有，所以a[1] = 99;
: 第2步. 100 ：binary search 最大一个<=100的，就是a[1]， 所以a[2] = 100;（意
: 思是现在长度为2的不减数列最少是100结尾）
: 第3步. 100 ：binary search 最大一个<=100的，是a[2]，所以a[3] = 100;
: 第4步. 1 : binary search 最大一个<=1的，没有，所以a[1] = 1;
|
s*****n
发帖数: 350 | 13 妙哉！
【在 x****r 的大作中提到】
: wiki里面那个还稍微麻烦了，他那样是可以retrieve这个sequence的方法，如果只需要
: 长度，可以这样做
: 数组a[i]里面可以存长度为i的子序列，最小的结尾是多少
: 基本是这样
: 数组： 99 100 100 1 2 3 4
: 第1步. 99 ：binary search 最大一个<=99的，没有，所以a[1] = 99;
: 第2步. 100 ：binary search 最大一个<=100的，就是a[1]， 所以a[2] = 100;（意
: 思是现在长度为2的不减数列最少是100结尾）
: 第3步. 100 ：binary search 最大一个<=100的，是a[2]，所以a[3] = 100;
: 第4步. 1 : binary search 最大一个<=1的，没有，所以a[1] = 1;
|
