r********7
发帖数: 42 | 1 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
我的解法是sort this sequence X to Y, Get the LCS of X and Y.
Time = O(nlogn + n^2) = O(N^2)
对方说还能更快。谁知道该怎么改进？
Updated: 我忘了说了，是求*最长*单调上升子列 | a**********s
发帖数: 588 | 2 求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到. | r********7
发帖数: 42 | 3 linear time 怎么找？
【在 a**********s 的大作中提到】
: 求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到.
| h*********i
发帖数: 116 | 4 是求所有单调升子序列还是一个就行啊
如果一个子序列就行的话，那就是linear阿，贪心法就行。
【在 r********7 的大作中提到】
: linear time 怎么找？
| r********7
发帖数: 42 | 5 一个就行。
假设 X=[0,2,0,4,3,1,5,0];
Y sorted by X = [0,0,0,1,2,3,4,5]
如何greedy求LCS？
【在 h*********i 的大作中提到】
: 是求所有单调升子序列还是一个就行啊
: 如果一个子序列就行的话，那就是linear阿，贪心法就行。
| h*********i
发帖数: 116 | 6 就是线形由左至右扫描。。。总是保留当前序列最大值。。然后看下一个元素是否比当
前序列中最大值大。。如果有比这个最大值大的就把这个元素加入子序列如果没有这个
最大值大就跳过但前元素再往下看。一直到所有元素都被扫描完。这样就是一格单调升
序列了。。。
【在 r********7 的大作中提到】
: 一个就行。
: 假设 X=[0,2,0,4,3,1,5,0];
: Y sorted by X = [0,0,0,1,2,3,4,5]
: 如何greedy求LCS？
| h*********i
发帖数: 116 | 7 好像不用求lcs lcs怎么也得用到dp把，那样就不是线形了。 | r********7
发帖数: 42 | 8 这个会不会有问题，比方说X=[3,2,1,0,1,2]
线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
但正确结果因该是[0,1,2]
【在 h*********i 的大作中提到】
: 就是线形由左至右扫描。。。总是保留当前序列最大值。。然后看下一个元素是否比当
: 前序列中最大值大。。如果有比这个最大值大的就把这个元素加入子序列如果没有这个
: 最大值大就跳过但前元素再往下看。一直到所有元素都被扫描完。这样就是一格单调升
: 序列了。。。
| p*********a
发帖数: 21 | 9 用数列d[]维护一个单调上升序列. 每读取一个新的数后，如果f[len]
中, len++; 否则找到某个i使得x>d[i]且x<=d[i+1]，用x去更新f[i+1]；最后看d数列
有多长就行了。
d单增，所以每次查找索引i时可以用二分查找，因此时间复杂度为O(nlogn)。
举个例子，假如序列为 2 5 3 4, 则d数列如下
2
2 5
2 3
2 3 4
最后，d的长度为3，LIS is 3。
不过，最后的d不一定是最长上升子序列的答案。
【在 r********7 的大作中提到】
: 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
: 我的解法是sort this sequence X to Y, Get the LCS of X and Y.
: Time = O(nlogn + n^2) = O(N^2)
: 对方说还能更快。谁知道该怎么改进？
: Updated: 我忘了说了，是求*最长*单调上升子列
| j*********h
发帖数: 21 | 10 1. number all the element in the original array, in growing sequence (O(n)).
e.g. original array is [3,2,1,0,1,2], after numbering, it became [(3,0),
(2,1),(1,2),(0,3),(1,4),(2,5)].
the "number" of each element is the corresponding position it is in the
original array.
2. after numbering, sort the new array according to their original value ,
using quicksort. (O(nlogn))
e.g. after sorting, [3,2,1,0,1,2]->[0,1,1,2,2,3]. ( I didn't list the "
position" of each element here).
3. find the lo
【在 r********7 的大作中提到】
: 这个会不会有问题，比方说X=[3,2,1,0,1,2]
: 线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
: 但正确结果因该是[0,1,2]
| | | h*********i
发帖数: 116 | 11 对需要一些改进
如果结果只有一个元素
可以线形扫描看整个序列是不是单调减，如果是自然单调升就是一个元素
如果不是就把违反单调减的那两个元素拿出来
作为初始的字序列的前两项就好了
。。。。。。。。。就是一个单调升
这样也是合乎题意的，不过感觉这样做就没什么意思了。
我觉得如果问最长单调升子序列查找更有意义，是不是
应该是最长单调升序列查找阿。
【在 r********7 的大作中提到】
: 这个会不会有问题，比方说X=[3,2,1,0,1,2]
: 线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
: 但正确结果因该是[0,1,2]
| g*******y
发帖数: 1930 | 12 3跟本问题难道不是等价的？？？
).
),
【在 j*********h 的大作中提到】
: 1. number all the element in the original array, in growing sequence (O(n)).
: e.g. original array is [3,2,1,0,1,2], after numbering, it became [(3,0),
: (2,1),(1,2),(0,3),(1,4),(2,5)].
: the "number" of each element is the corresponding position it is in the
: original array.
: 2. after numbering, sort the new array according to their original value ,
: using quicksort. (O(nlogn))
: e.g. after sorting, [3,2,1,0,1,2]->[0,1,1,2,2,3]. ( I didn't list the "
: position" of each element here).
: 3. find the lo
| g*******y
发帖数: 1930 | 13 你只维护一个数组，肯定是不对的
eg，4 5 6 1 2 3 4
f
【在 p*********a 的大作中提到】
: 用数列d[]维护一个单调上升序列. 每读取一个新的数后，如果f[len]: 中, len++; 否则找到某个i使得x>d[i]且x<=d[i+1]，用x去更新f[i+1]；最后看d数列
: 有多长就行了。
: d单增，所以每次查找索引i时可以用二分查找，因此时间复杂度为O(nlogn)。
: 举个例子，假如序列为 2 5 3 4, 则d数列如下
: 2
: 2 5
: 2 3
: 2 3 4
: 最后，d的长度为3，LIS is 3。
| p*********a
发帖数: 21 | 14 一般来LIS只需要求出长度, 这个方法足够了, 我强调了d的结果并不是最后要求的LIS.
【在 g*******y 的大作中提到】
: 你只维护一个数组，肯定是不对的
: eg，4 5 6 1 2 3 4
:
: f
| s****i
发帖数: 150 | 15 不可以sort吧。假设4,5,6,1,2,3，最长子列是4,5,6或者1,2,3，你sort了之后不就变
成1,2,3,4,5,6了。。。
这个用DP好了 | j*********h
发帖数: 21 | 16 no.
in step3 , all elements have already been sorted.
for example,
[3,2,1,0,1,2]->[0,1,1,2,2,3]
actually, if I write out each element in the format (value, position), the
above will become
[(3,1),(2,2) ,(1,3),(0,4),(1,5),(2,6)]->[(0,4),(1,3),(1,5),(2,2) ,(2,6),(3,1
)].
in the resulting array, when scanning, you will get (0,4) first, put it in
resulting queue 1.
then you get (1,3), since (3<4),you will dump (0,4), put (1,3) in queue 1
then you get (1,5), keep it in queue1.. since 5>3
then you
【在 g*******y 的大作中提到】
: 3跟本问题难道不是等价的？？？
:
: ).
: ),
| j*********h
发帖数: 21 | 17 the reason not to dump (2,2) is that we already have 2 elements in queue2,
in this case, if you dump 2 elements in exchange for 1 element, it would be
worse.
the
,1
in
【在 j*********h 的大作中提到】
: no.
: in step3 , all elements have already been sorted.
: for example,
: [3,2,1,0,1,2]->[0,1,1,2,2,3]
: actually, if I write out each element in the format (value, position), the
: above will become
: [(3,1),(2,2) ,(1,3),(0,4),(1,5),(2,6)]->[(0,4),(1,3),(1,5),(2,2) ,(2,6),(3,1
: )].
: in the resulting array, when scanning, you will get (0,4) first, put it in
: resulting queue 1.
| z********y
发帖数: 109 | 18 public static int MCSS(int [] a) {
int max = 0, sum = 0, start = 0, end = 0, i=0;
// Cycle through all possible end indexes.
for (j = 0; j < a.length; j++) {
sum += a[j]; // No need to re-add all values.
if (sum > max) {
max = sum;
start = i; // Although method doesn't return these
end = j; // they can be computed.
}
else if (sum < 0) {
i = j+1; // Only possible MCSSs start with an index >j.
s
【在 r********7 的大作中提到】
: 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
: 我的解法是sort this sequence X to Y, Get the LCS of X and Y.
: Time = O(nlogn + n^2) = O(N^2)
: 对方说还能更快。谁知道该怎么改进？
: Updated: 我忘了说了，是求*最长*单调上升子列
| y*******g
发帖数: 6599 | 19 你这个是什么?
【在 z********y 的大作中提到】
: public static int MCSS(int [] a) {
: int max = 0, sum = 0, start = 0, end = 0, i=0;
: // Cycle through all possible end indexes.
: for (j = 0; j < a.length; j++) {
: sum += a[j]; // No need to re-add all values.
: if (sum > max) {
: max = sum;
: start = i; // Although method doesn't return these
: end = j; // they can be computed.
: }
| j*****j
发帖数: 115 | | | | z********y
发帖数: 109 | 21 haha
看错了。这个可以用suffix tree做吧
【在 y*******g 的大作中提到】
: 你这个是什么?
| c******f
发帖数: 2144 | | d****j
发帖数: 293 | 23 ...这道题是非常经典的算法题了，网上讨论的有很多，大家应该记住（我也忘了，貌似2年前看到的了）。google: "nlogn的最长子序列算法"
我把答案和分析zz到这里吧(具体的代码网上自己搜):
这是一个很好的题目。题目的算法还是比较容易看出来的，就是求最长上升子序列的长
度。不过这一题的数据规模最大可以达到40000，经典的O(n^2)的动态规划算法明显会
超时。我们需要寻找更好的方法来解决是最长上升子序列问题。
先回顾经典的O(n^2)的动态规划算法，设A[i]表示序列中的第i个数，F[i]表示从1
到i这一段中以i结尾的最长上升子序列的长度，初始时设F[i] = 0(i = 1, 2, ...,
len(A))。则有动态规划方程：F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且
A[j] < A[i])。
现在，我们仔细考虑计算F[i]时的情况。假设有两个元素A[x]和A[y]，满足
(1)x < y < I (2)A[x] < A[y] < A[i] (3)F[x] = F[y]
此时，选择F[x]和选择F[y]都可以得到 |
|
