c********t
发帖数: 5706 | 1 不用binary O(n^2) 可以输出结果数组。
用了binary，我只会求出最大长度 O(nlogn)，无法输出最终结果数组,谁见过解法？ |
H****s
发帖数: 247 | 2 查看下面链接：
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
【在 c********t 的大作中提到】
: 不用binary O(n^2) 可以输出结果数组。
: 用了binary，我只会求出最大长度 O(nlogn)，无法输出最终结果数组,谁见过解法？
|
c********t
发帖数: 5706 | |
C***U
发帖数: 2406 | 4 我最近想出来一个dp的做法
感觉的比那个wiki上的解法要更自然一点
【在 c********t 的大作中提到】
: 不用binary O(n^2) 可以输出结果数组。
: 用了binary，我只会求出最大长度 O(nlogn)，无法输出最终结果数组,谁见过解法？
|
c********t
发帖数: 5706 | 5 求解，我想到的dp都是O(n^2)的
【在 C***U 的大作中提到】
: 我最近想出来一个dp的做法
: 感觉的比那个wiki上的解法要更自然一点
|
C***U
发帖数: 2406 | 6 我给你举个例子说一下我的想法，顺便版上的大牛们可以看看我的想法对不对，我经常
会想错问题
例子： 5 4 3 2 1 3 4
有一个lists里面的元素是array
1. 5进来，这时候lists是空的，所以我就把5放入到一个array，然后插入到lists里面
这时候lists就是
a) 5
2. 4进来，这时候我们用lists里面的array的最后一个数字来2分查找，因为现在lists
里面只有5，所以我们应该把4单独作为一个array放到lists里面，这时候lists就是
a)4
b)5
3. 3 2 1进来的时候，像前面一样，2分查找到自己的位置，lists变成
a) 1
b) 2
c) 3
d) 4
e) 5
4. 第二个3进来的时候，我们2分查找，会发现3应该放入所有d)前面的array里面。然
而当3放入以后我们没有必要全部保留前面的array，而是只要保留最长的那个，所以当
第二个3放入以后，lists就变成了
a) 1 3
b) 4
c) 5
5 当第二个4进来的时候，我们还是像前面查找，我们发现4应该放入a) b)里面，然后
我们只要保留最长的那个。所以当第二个4放进来以后，我们的lists就变成了
a) 1 3 4
b) 5
这个算法的时间复杂度要用到potential method,稍微有点复杂. potential function
是每一步lists里面array的个数. 空间是O(n),因为在每个时候,一个数字只出现在
lists里面一次.时间是O(nlogn)，因为根据potential function，每一步用到O(logn)
的时间。
不知道这个算法和wiki上那个是不是一样.
【在 c********t 的大作中提到】
: 求解，我想到的dp都是O(n^2)的
|
c********t
发帖数: 5706 | 7 我觉得行，而且挺好懂得，第5步你删掉
数小于i的也该删去，2,3步都可以这样做，这样5,4,3,2,1做完只剩
a) 1
更简单，而且省空间。再看看有没有大牛指点。
lists
【在 C***U 的大作中提到】
: 我给你举个例子说一下我的想法，顺便版上的大牛们可以看看我的想法对不对，我经常
: 会想错问题
: 例子： 5 4 3 2 1 3 4
: 有一个lists里面的元素是array
: 1. 5进来，这时候lists是空的，所以我就把5放入到一个array，然后插入到lists里面
: 这时候lists就是
: a) 5
: 2. 4进来，这时候我们用lists里面的array的最后一个数字来2分查找，因为现在lists
: 里面只有5，所以我们应该把4单独作为一个array放到lists里面，这时候lists就是
: a)4
|
c********t
发帖数: 5706 | 8 再想想，不对呀。如果1 4 2 3 ，你是什么步骤？
lists
【在 C***U 的大作中提到】
: 我给你举个例子说一下我的想法，顺便版上的大牛们可以看看我的想法对不对，我经常
: 会想错问题
: 例子： 5 4 3 2 1 3 4
: 有一个lists里面的元素是array
: 1. 5进来，这时候lists是空的，所以我就把5放入到一个array，然后插入到lists里面
: 这时候lists就是
: a) 5
: 2. 4进来，这时候我们用lists里面的array的最后一个数字来2分查找，因为现在lists
: 里面只有5，所以我们应该把4单独作为一个array放到lists里面，这时候lists就是
: a)4
|
C***U
发帖数: 2406 | 9 恩。。。这个例子有问题
应该是原来的保留，然后在最长的后面增加那个数字
【在 c********t 的大作中提到】
: 再想想，不对呀。如果1 4 2 3 ，你是什么步骤？
:
: lists
|
c********t
发帖数: 5706 | 10 俺证实了你的想法可行，而且直观，其实用二维数组即可，不用list.
wiki上的我怎么也实现不了
【在 C***U 的大作中提到】
: 恩。。。这个例子有问题
: 应该是原来的保留，然后在最长的后面增加那个数字
|
|
|
c********t
发帖数: 5706 | 11 不用binary O(n^2) 可以输出结果数组。
用了binary，我只会求出最大长度 O(nlogn)，无法输出最终结果数组,谁见过解法？ |
H****s
发帖数: 247 | 12 查看下面链接：
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
【在 c********t 的大作中提到】
: 不用binary O(n^2) 可以输出结果数组。
: 用了binary，我只会求出最大长度 O(nlogn)，无法输出最终结果数组,谁见过解法？
|
c********t
发帖数: 5706 | |
C***U
发帖数: 2406 | 14 我最近想出来一个dp的做法
感觉的比那个wiki上的解法要更自然一点
【在 c********t 的大作中提到】
: 不用binary O(n^2) 可以输出结果数组。
: 用了binary，我只会求出最大长度 O(nlogn)，无法输出最终结果数组,谁见过解法？
|
c********t
发帖数: 5706 | 15 求解，我想到的dp都是O(n^2)的
【在 C***U 的大作中提到】
: 我最近想出来一个dp的做法
: 感觉的比那个wiki上的解法要更自然一点
|
C***U
发帖数: 2406 | 16 我给你举个例子说一下我的想法，顺便版上的大牛们可以看看我的想法对不对，我经常
会想错问题
例子： 5 4 3 2 1 3 4
有一个lists里面的元素是array
1. 5进来，这时候lists是空的，所以我就把5放入到一个array，然后插入到lists里面
这时候lists就是
a) 5
2. 4进来，这时候我们用lists里面的array的最后一个数字来2分查找，因为现在lists
里面只有5，所以我们应该把4单独作为一个array放到lists里面，这时候lists就是
a)4
b)5
3. 3 2 1进来的时候，像前面一样，2分查找到自己的位置，lists变成
a) 1
b) 2
c) 3
d) 4
e) 5
4. 第二个3进来的时候，我们2分查找，会发现3应该放入所有d)前面的array里面。然
而当3放入以后我们没有必要全部保留前面的array，而是只要保留最长的那个，所以当
第二个3放入以后，lists就变成了
a) 1 3
b) 4
c) 5
5 当第二个4进来的时候，我们还是像前面查找，我们发现4应该放入a) b)里面，然后
我们只要保留最长的那个。所以当第二个4放进来以后，我们的lists就变成了
a) 1 3 4
b) 5
这个算法的时间复杂度要用到potential method,稍微有点复杂. potential function
是每一步lists里面array的个数. 空间是O(n),因为在每个时候,一个数字只出现在
lists里面一次.时间是O(nlogn)，因为根据potential function，每一步用到O(logn)
的时间。
不知道这个算法和wiki上那个是不是一样.
【在 c********t 的大作中提到】
: 求解，我想到的dp都是O(n^2)的
|
c********t
发帖数: 5706 | 17 我觉得行，而且挺好懂得，第5步你删掉
数小于i的也该删去，2,3步都可以这样做，这样5,4,3,2,1做完只剩
a) 1
更简单，而且省空间。再看看有没有大牛指点。
lists
【在 C***U 的大作中提到】
: 我给你举个例子说一下我的想法，顺便版上的大牛们可以看看我的想法对不对，我经常
: 会想错问题
: 例子： 5 4 3 2 1 3 4
: 有一个lists里面的元素是array
: 1. 5进来，这时候lists是空的，所以我就把5放入到一个array，然后插入到lists里面
: 这时候lists就是
: a) 5
: 2. 4进来，这时候我们用lists里面的array的最后一个数字来2分查找，因为现在lists
: 里面只有5，所以我们应该把4单独作为一个array放到lists里面，这时候lists就是
: a)4
|
c********t
发帖数: 5706 | 18 再想想，不对呀。如果1 4 2 3 ，你是什么步骤？
lists
【在 C***U 的大作中提到】
: 我给你举个例子说一下我的想法，顺便版上的大牛们可以看看我的想法对不对，我经常
: 会想错问题
: 例子： 5 4 3 2 1 3 4
: 有一个lists里面的元素是array
: 1. 5进来，这时候lists是空的，所以我就把5放入到一个array，然后插入到lists里面
: 这时候lists就是
: a) 5
: 2. 4进来，这时候我们用lists里面的array的最后一个数字来2分查找，因为现在lists
: 里面只有5，所以我们应该把4单独作为一个array放到lists里面，这时候lists就是
: a)4
|
C***U
发帖数: 2406 | 19 恩。。。这个例子有问题
应该是原来的保留，然后在最长的后面增加那个数字
【在 c********t 的大作中提到】
: 再想想，不对呀。如果1 4 2 3 ，你是什么步骤？
:
: lists
|
c********t
发帖数: 5706 | 20 俺证实了你的想法可行，而且直观，其实用二维数组即可，不用list.
wiki上的我怎么也实现不了
【在 C***U 的大作中提到】
: 恩。。。这个例子有问题
: 应该是原来的保留，然后在最长的后面增加那个数字
|
|
|
a**********e
发帖数: 157 | 21 stackoverflow这个很简洁易懂
http://stackoverflow.com/questions/6129682/longest-increasing-s
【在 c********t 的大作中提到】
: 俺证实了你的想法可行，而且直观，其实用二维数组即可，不用list.
: wiki上的我怎么也实现不了
|
C***U
发帖数: 2406 | 22 恩
这个很强
set st;
set::iterator it;
st.clear();
for(i=0; i
st.insert(array[i]);
it=st.find(array[i]);
it++;
if(it!=st.end()) st.erase(it);
}
cout<
【在 a**********e 的大作中提到】
: stackoverflow这个很简洁易懂
: http://stackoverflow.com/questions/6129682/longest-increasing-s
|
c********t
发帖数: 5706 | |
l*****a
发帖数: 559 | 24 1 2 3 4 5 6 7 9 3 8 11 4 5 6 4 19 7 1 7 17 12 16
测试了一下，
跑不出正确答案。
错误结果是st.size() = 7
【在 C***U 的大作中提到】
: 恩
: 这个很强
: set st;
: set::iterator it;
: st.clear();
: for(i=0; i: st.insert(array[i]);
: it=st.find(array[i]);
: it++;
: if(it!=st.end()) st.erase(it);
|
l*******b
发帖数: 2586 | 25 想输出那个序列得要有一个数组记录每个数值在数列中之前的那个值,所以要多开一个
数组记录这个信息吧.
每次用binary search push进去一个之后那个数之前的一个数就是这个. 写得太烂了,
有空重写一下.
class Solution {
private:
vector s;
vector pre;
int push(int k) {
if(s.empty()){
s.push_back(k);
return -1;
}
if(k >= s.back()){
s.push_back(k);
return s[s.size()-2];
}
int l = 0, r = s.size()-1, mid;
while(l < r)
(s[mid = (l+r)/2] > k) ? r = mid : l = mid+1;
s[r] = k;
return (r-1 >= 0) ? s[r-1] : -1;
}
public:
int max_inc_seq (int a[], int n) {
int i;
for(i = 0; i < n; ++i)
pre.push_back(push(a[i]));
cout << "longest increasing: " << s.size() << '\n';
int pt = s.back();
i = n - 1;
while(pt != -1) {
cout << pt << " ";
for(; a[i] != pt ; i-- );
pt = pre[i--];
}
cout << '\n';
s.clear();
pre.clear();
return 0;
}
}; |
