l**d
发帖数: 746 | 1 一个任意的数组，找出一个严格单调递增的最长子序列。
例如: { 3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8 } –> output： {0, 1, 2, 4, 5, 6, 8}
网上看到人说有个很简洁巧妙的算法，能在O(N log N)时间和O(N)空间做出来！方法就
是始终保持一个单增的序列，然后新来的数如果比当前最大还大就append在后面，否则
在单增序列里面做binary search，替换相应位置的数。
比如给定src[ ]:
3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8
定义一个新数组，value a[i]是当前数src[i]在包含自己的最长序列里的index。如果
src[i] > src[i-1], 那么a[i] = a[i-1] + 1, 否则，binary search 找到src[i] <
src[k-1],
src: 3, 0, 1, 7, 2, 4, 9, 10, 5, 15, 8
a: 1 1 2 3 3 4 5 6 5 7 6
可是我觉得这个方法不对啊，举个简单例子：给
src: {7， 8， 1， 10}
a: 1 2 1 ?
按照他的算法，到10的时候src[i] > src[i-1], 那么a[i] = a[i-1] + 1
可是10应该是从前面8开始算。那个binary search 怎么回事，我也没看明白。 | d*******3
发帖数: 58 | 2 nlogn的不是这么做的，你想想你的a数组都不是有序的，怎么能binary search呢？
nlogn的是用数组a[i] 保存长度为i的递增序列末尾的最小元素，后面通过二分查找来
维护这个递增数组。
你的例子里不太明显，我换个
src:
2 9 7 3 8 5 10
a id:
0 1 2 3 4
2
2 9
2 7
2 3
2 3 8
2 3 5
2 3 5 10
这样最后递增序列长度为4 | s**x
发帖数: 7506 | 3 Solution 2:
O(n log k) algorithm. K is the length of We have elements.
Assume we already have an increasing sequence: A1, A2, A3, …., for any
given element E, we either
can simply append E to make the list longer,
Do a binary search to find a position j such that A[j] < E < A[j+1], update
A[j+1] to E, so A[1..j+1] can get longer later with new element.
Another list P is used to stores the position of the predecessor element
in the longest increasing subsequence.
#include
using namespace std;
void find_lis(vector &a,
vector &b)
{
vector p(a.size());
int u, v;
if (a.empty()) return;
b.push_back(0);
for (size_t i = 1; i < a.size(); i++) {
/* If next element a[i] is greater than last element of
current longest subsequence a[b.back()], just push it at back of "b" and
continue */
if (a[b.back()] < a[i]) {
p[i] = b.back(); b.push_back(i);
continue;
}
/* Binary search to find the smallest element referenced by b which
is just bigger than a[i]
Note : Binary search is performed on b (and not a). Size of b is
always <=k and hence contributes O(log k) to complexity. */
for (u = 0, v = b.size()-1; u < v;) {
int c = (u + v) / 2;
if (a[b[c]] < a[i]) u=c+1; else v=c;
}
/* Update b if new value is smaller then previously referenced
value */
if (a[i] < a[b[u]]) {
if (u > 0) p[i] = b[u-1];
/* this will not corrupt existing LIS which is tracked by list p. */
b[u] = i;
}
} // end for loop
for (u = b.size(), v = b.back(); u--; v = p[v])
b[u] = v;
} | s**x
发帖数: 7506 | 4 这个题挺难的， 忘了从哪 找到的 code, 看了好多遍才看懂。 | d**********x
发帖数: 4083 | 5 http://dp2.me/blog/?p=144
【在 s**x 的大作中提到】
: 这个题挺难的， 忘了从哪 找到的 code, 看了好多遍才看懂。
| z****p
发帖数: 18 | 6
I figured out an O(n log n) algorithm. Obviously it's not as efficient as
duckling3's solution.
-First, sort the elements, which takes O(n log n)
-Second, visit the elements from the smallest to the largest, along the
visits, stretch several "rubber bands" (where the number of rubber bands is
up to K, with K being the size of the resulting max subsequence)
++all the rubber bands have their "right ends" at position N (outside the
array)
++we try to stretch the "left ends" of the rubber bands to as far left as
possible
++the 1st rubber band is longer than the 2nd one, which in turn is longer
than the 3rd one, and so on
++we use a binary tree to store the rubber bands' left ends, where the index
key is the location of the left ends
-When visiting the next element (according to the sorted order),
say it's position in the array is j
++we use a binary search to find the rubber band whose left end is
immediately to the right of j
++if j is smaller than the left end of the 1st rubber band,
we simply stretch the 1st rubber band by changing the left end of it to j,
++if j is bigger than the left ends of all the current rubber bands, we
start a new rubber band, and set its left end to j
++otherwise, we stretch the rubber band whose left end is immediately on
the right of j, by moving the rubber band's left end to j
-After visiting all the elements in sorted order and stretching the rubber
bands along the visits, the number of rubber bands K is the number
of elements in the max increasing subsequence.
-However, to get the exact subsequence, we have to revise the above
algorithm by adding a bookkeeping: when we stretch the k-th rubber band, we
need to
remember the location of the current location of the left end of the (k-1)-
th rubber band. Then we can trace back the bookkeeping pointers starting
from
that of the K-th rubber band.
【在 d*******3 的大作中提到】
: nlogn的不是这么做的，你想想你的a数组都不是有序的，怎么能binary search呢？
: nlogn的是用数组a[i] 保存长度为i的递增序列末尾的最小元素，后面通过二分查找来
: 维护这个递增数组。
: 你的例子里不太明显，我换个
: src:
: 2 9 7 3 8 5 10
: a id:
: 0 1 2 3 4
: 2
: 2 9
|
|
