B*****t
发帖数: 335 | 1 收尾相接的序列有什么好的算法求最长递增子序列的长度？ | x***y
发帖数: 633 | 2 put 2 copies together...
【在 B*****t 的大作中提到】
: 收尾相接的序列有什么好的算法求最长递增子序列的长度？
| c**l
发帖数: 2661 | 3 据对DP吧
我好像刚看过
每个点连向他后面的 最近的比他大的
然后最短路径
【在 B*****t 的大作中提到】
: 收尾相接的序列有什么好的算法求最长递增子序列的长度？
| B*****t
发帖数: 335 | 4 复杂度？
【在 x***y 的大作中提到】
: put 2 copies together...
| x***y
发帖数: 633 | 5 put one copy of the array after the other, and use O(nlogn) LIS and of the
result, find the longest subsequence that does not overlap with itself in original array O(nlogn) with binary search...So, totaly time is O(nlogn)...
【在 B*****t 的大作中提到】
: 复杂度？
| B*****t
发帖数: 335 | 6 find the longest subsequence that does not overlap with itself in
original array
这是什么意思？怎么find？O(nlogn)的方法不能直接拿过来用。二分的时候你要维护一
个数列的值，但是你怎么知道哪些需要更新，哪些不要？而且队列组成了一个环，二分被
更新掉的数据在后边可能会用到，你怎么把它恢复？
and of the
itself in original array O(nlogn) with binary search...So, totaly
time is O(nlogn)...
【在 x***y 的大作中提到】
: put one copy of the array after the other, and use O(nlogn) LIS and of the
: result, find the longest subsequence that does not overlap with itself in original array O(nlogn) with binary search...So, totaly time is O(nlogn)...
| B*****t
发帖数: 335 | 7 这个貌似可行！应该是求最长路吧？
【在 c**l 的大作中提到】
: 据对DP吧
: 我好像刚看过
: 每个点连向他后面的 最近的比他大的
: 然后最短路径
| r****o
发帖数: 1950 | 8 不懂，能不能解释一下?
【在 B*****t 的大作中提到】
: 这个貌似可行！应该是求最长路吧？
| B*****t
发帖数: 335 | 9 又想了一下，觉得记录每个点连向他前面的最近的比他大的点的贪心方法是行不通的。
比如
..7 9..1 10
贪心的话10连向1，可是10连向9的时候的序列更长
【在 r****o 的大作中提到】
: 不懂，能不能解释一下?
| x******3
发帖数: 245 | 10 序列头可以是任意元素吗
【在 B*****t 的大作中提到】
: 收尾相接的序列有什么好的算法求最长递增子序列的长度？
| | | B*****t
发帖数: 335 | 11 可以想象成为n个大于0的整数序列
【在 x******3 的大作中提到】
: 序列头可以是任意元素吗
| x******3
发帖数: 245 | 12 那brute force就是对每一个可能的序列作LIS吗？多谢
【在 B*****t 的大作中提到】
: 可以想象成为n个大于0的整数序列
| B*****t
发帖数: 335 | 13 恩。 brute force的方法是O(n^2logn)的，显然不是很好。
【在 x******3 的大作中提到】
: 那brute force就是对每一个可能的序列作LIS吗？多谢
| r****o
发帖数: 1950 | 14 这题是不是你自己想的？ 呵呵。
【在 B*****t 的大作中提到】
: 恩。 brute force的方法是O(n^2logn)的，显然不是很好。
| x***y
发帖数: 633 | 15 It means that if we put 2 arrays together, the region that the LIS in may
overlap with itself. E.g if the array is 5 1 6 2 7 3 8 4, we can get
LIS is 8, but actually it should be 5.....So, after finding the LIS of the 2
combined arrays, we need the longest part of it that can exist in a
circular array. The way to do this is arrange the indices of the LIS
sequence, like above, 1 3 5 7 0 2 4 6, and use O(n) to find the first
nonincreasing index (0 here) and use binary search to find the corre
【在 B*****t 的大作中提到】
: find the longest subsequence that does not overlap with itself in
: original array
: 这是什么意思？怎么find？O(nlogn)的方法不能直接拿过来用。二分的时候你要维护一
: 个数列的值，但是你怎么知道哪些需要更新，哪些不要？而且队列组成了一个环，二分被
: 更新掉的数据在后边可能会用到，你怎么把它恢复？
:
: and of the
: itself in original array O(nlogn) with binary search...So, totaly
: time is O(nlogn)...
| c****l
发帖数: 1280 | | B*****t
发帖数: 335 | 17 thanks a lot for your comment!
but there are still 2 things not clear to me.
1. how can you prove that the LIS in the circular array is a
subset of the LIS in the doubled array, or the length of LIS in
the circular array is equal to the length of some sub-array of
the LIS in the doubled array, such that the sub-array is a legal
LIS in the circular array?
2. In the extreme case, there are might be multiple equal length
LIS in the doubled array, which might approach O(n), and the
second step in yo
【在 x***y 的大作中提到】
: It means that if we put 2 arrays together, the region that the LIS in may
: overlap with itself. E.g if the array is 5 1 6 2 7 3 8 4, we can get
: LIS is 8, but actually it should be 5.....So, after finding the LIS of the 2
: combined arrays, we need the longest part of it that can exist in a
: circular array. The way to do this is arrange the indices of the LIS
: sequence, like above, 1 3 5 7 0 2 4 6, and use O(n) to find the first
: nonincreasing index (0 here) and use binary search to find the corre
| B*****t
发帖数: 335 | 18 不是我自己想的。很久以前的一个算法题，一直没想到好的方法。
【在 r****o 的大作中提到】
: 这题是不是你自己想的？ 呵呵。
| B*****t
发帖数: 335 | 19 问题是怎么控制长度不超过n的子数组，使复杂度小于O(n^2logn)
【在 r****o 的大作中提到】
: 这题是不是你自己想的？ 呵呵。
| r****o
发帖数: 1950 | 20 我的意思是说我们求这个新数组的最长连续增长子序列，在这个过程中如果我们得到的
最长连续增长子序列的长度达到了n，就返回当前的结果，否则继续找。
可能我想的简单了，欢迎拍砖。
【在 B*****t 的大作中提到】
: 问题是怎么控制长度不超过n的子数组，使复杂度小于O(n^2logn)
| | | r****o
发帖数: 1950 | 21 为什么没人回复呢？是不是这个想法被BS了?
【在 r****o 的大作中提到】
: 我的意思是说我们求这个新数组的最长连续增长子序列，在这个过程中如果我们得到的
: 最长连续增长子序列的长度达到了n，就返回当前的结果，否则继续找。
: 可能我想的简单了，欢迎拍砖。
| B*****t
发帖数: 335 | 22 最长连续增长子序列的长度不一定是n，也许比n小。你这个方法还是brute force的。
【在 r****o 的大作中提到】
: 我的意思是说我们求这个新数组的最长连续增长子序列，在这个过程中如果我们得到的
: 最长连续增长子序列的长度达到了n，就返回当前的结果，否则继续找。
: 可能我想的简单了，欢迎拍砖。
| r****o
发帖数: 1950 | 23 我刚才想太简单了不好意思。
【在 B*****t 的大作中提到】
: 最长连续增长子序列的长度不一定是n，也许比n小。你这个方法还是brute force的。
| s*********s
发帖数: 318 | 24 我的土方法：
假设从一个点开始找最长递增序列到 和这个点前面的点。一个完整的树列。
再从中间点开始，找最长递增序列 到和中间点前面的点。
哪个最长递增序列长，就选哪个， | K******g
发帖数: 1870 | 25 这个不对
例如：
4 6 5 5.5 7 2 8 9 1 3
按照你的方法，最长的应该是4 6 7 8 9
但是其实，最长的是 4 5 5.5 7 8 9
【在 c**l 的大作中提到】
: 据对DP吧
: 我好像刚看过
: 每个点连向他后面的 最近的比他大的
: 然后最短路径
| r****o
发帖数: 1950 | 26 我有个想法不知道对不对，
假定有个数组是
7,2,-1,3,0,4,-2,6,-2,0,-1,1
我们先找到它的最长递增子序列是2,3,4,6, 包含这个子序列的子数组是2,-1,3,0,4,-2
,6
不属于这个子数组的其他元素是7和-2,0,-1,1
然后我们考虑两种情形，
一种是把这些元素加到子数组左边，即 -2,0,-1,1,7,2,-1,3,0,4,-2,6
另一种是把这些元素加到子数组右边，即2,-1,3,0,4,-2,6,-2,0,-1,1,7
然后找这两个新数组的最长递增子序列，取最长的那个作答案。这里是-2,-1,1,2,3,4,
6.
感觉这个方案不一定对，而且可能你也想过这个方法了。如果不对的话，能否给出反例?
分被
【在 B*****t 的大作中提到】
: find the longest subsequence that does not overlap with itself in
: original array
: 这是什么意思？怎么find？O(nlogn)的方法不能直接拿过来用。二分的时候你要维护一
: 个数列的值，但是你怎么知道哪些需要更新，哪些不要？而且队列组成了一个环，二分被
: 更新掉的数据在后边可能会用到，你怎么把它恢复？
:
: and of the
: itself in original array O(nlogn) with binary search...So, totaly
: time is O(nlogn)...
| r****o
发帖数: 1950 | 27 有没有谁评价一下我的想法对不对？
欢迎拍砖。
-2
4,
【在 r****o 的大作中提到】
: 我有个想法不知道对不对，
: 假定有个数组是
: 7,2,-1,3,0,4,-2,6,-2,0,-1,1
: 我们先找到它的最长递增子序列是2,3,4,6, 包含这个子序列的子数组是2,-1,3,0,4,-2
: ,6
: 不属于这个子数组的其他元素是7和-2,0,-1,1
: 然后我们考虑两种情形，
: 一种是把这些元素加到子数组左边，即 -2,0,-1,1,7,2,-1,3,0,4,-2,6
: 另一种是把这些元素加到子数组右边，即2,-1,3,0,4,-2,6,-2,0,-1,1,7
: 然后找这两个新数组的最长递增子序列，取最长的那个作答案。这里是-2,-1,1,2,3,4,
| a***9
发帖数: 364 | 28 如果我理解的对的话，反例：
1，40，50，2，1， 3， 4， 5， 2， 3， 4
最长是1,2,3,4,5；
包含它的子数组是1,40,50,2,1,3,4,5
剩下的2,3,4加左加右都不能算得最长环子序列：1,2,3,4,40,50
-2
4,
【在 r****o 的大作中提到】
: 我有个想法不知道对不对，
: 假定有个数组是
: 7,2,-1,3,0,4,-2,6,-2,0,-1,1
: 我们先找到它的最长递增子序列是2,3,4,6, 包含这个子序列的子数组是2,-1,3,0,4,-2
: ,6
: 不属于这个子数组的其他元素是7和-2,0,-1,1
: 然后我们考虑两种情形，
: 一种是把这些元素加到子数组左边，即 -2,0,-1,1,7,2,-1,3,0,4,-2,6
: 另一种是把这些元素加到子数组右边，即2,-1,3,0,4,-2,6,-2,0,-1,1,7
: 然后找这两个新数组的最长递增子序列，取最长的那个作答案。这里是-2,-1,1,2,3,4,
| a***9
发帖数: 364 | 29 这题我搜了一下，好像最好的worst case就是要O(n^2logn)，有好一点的算法
但是approximate的
【在 B*****t 的大作中提到】
: 收尾相接的序列有什么好的算法求最长递增子序列的长度？
| r****o
发帖数: 1950 | 30 多谢，呵呵。
【在 a***9 的大作中提到】
: 如果我理解的对的话，反例：
: 1，40，50，2，1， 3， 4， 5， 2， 3， 4
: 最长是1,2,3,4,5；
: 包含它的子数组是1,40,50,2,1,3,4,5
: 剩下的2,3,4加左加右都不能算得最长环子序列：1,2,3,4,40,50
:
: -2
: 4,
| | | d****n
发帖数: 233 | 31 Since it's a circular sequence, we want to find the optimal start point in
this sequence, so that the LIS exists in it. we have two ways to solve it.
1. Start at arbitary element and form a sequence, repeat this sequence and
find the LIS from the new sequence of size 2N. of course, we can stop early
if a LIS with length N is find(if all the elements are the same in the
sequence). the complexity will be O(2N*Log(2N))
2. Start at arbitary element and form a sequence, find all the ending
eleme
【在 B*****t 的大作中提到】
: 收尾相接的序列有什么好的算法求最长递增子序列的长度？
| s*********t
发帖数: 1663 | 32 如果是non decreasing的话这个解法的正确性似乎有问题？
如果s=[1,0]
在s2=[1,0,1,0]中，1,1是一个子序列，但是不合法
还是我理解的部队？
in
and
early
.
【在 d****n 的大作中提到】
: Since it's a circular sequence, we want to find the optimal start point in
: this sequence, so that the LIS exists in it. we have two ways to solve it.
: 1. Start at arbitary element and form a sequence, repeat this sequence and
: find the LIS from the new sequence of size 2N. of course, we can stop early
: if a LIS with length N is find(if all the elements are the same in the
: sequence). the complexity will be O(2N*Log(2N))
: 2. Start at arbitary element and form a sequence, find all the ending
: eleme
| d****k
发帖数: 41 | 33 用DP方法如何？复杂度n^2，用i做数组索引，
所以下一个元素是（i+1) % size，这样就
很容易实现数组首尾相接，不用拷贝数组
【在 B*****t 的大作中提到】
: 收尾相接的序列有什么好的算法求最长递增子序列的长度？
| B*****t
发帖数: 335 | 34 could you please share your search result links? thanks.
【在 a***9 的大作中提到】
: 这题我搜了一下，好像最好的worst case就是要O(n^2logn)，有好一点的算法
: 但是approximate的
|
|
