有一件事我无法理解：
为什么 X[M[i]] 是非递减序列？
问问题
52270 次
8 回答
86
我们先来看n^2算法：
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
dp[i] = 1;
for( int j = 0; j < i; j++ ) {
if( array[i] > array[j] ) {
if( dp[i] < dp[j]+1 ) {
dp[i] = dp[j]+1;
}
}
}
}
现在改进发生在第二个循环，基本上，您可以通过使用二进制搜索来提高速度。除了数组dp[]，我们还有一个数组c[]，c很特别，c[i]的意思是：长度为i的最长递增序列的最后一个元素的最小值。
sz = 1;
c[1] = array[0]; /*at this point, the minimum value of the last element of the size 1 increasing sequence must be array[0]*/
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
if( array[i] < c[1] ) {
c[1] = array[i]; /*you have to update the minimum value right now*/
dp[i] = 1;
}
else if( array[i] > c[sz] ) {
c[sz+1] = array[i];
dp[i] = sz+1;
sz++;
}
else {
int k = binary_search( c, sz, array[i] ); /*you want to find k so that c[k-1]<array[i]<c[k]*/
c[k] = array[i];
dp[i] = k;
}
}
于 2011-09-30T18:13:59.620 回答
25
这是The Hitchhiker's Guide to the Programming Contests中的 O(n*lg(n)) 解决方案（注意：此实现假定列表中没有重复项）：
set<int> st;
set<int>::iterator it;
st.clear();
for(i=0; i<n; i++) {
st.insert(array[i]);
it=st.find(array[i]);
it++;
if(it!=st.end()) st.erase(it);
}
cout<<st.size()<<endl;
例如，为了解决重复问题，可以检查该数字是否已经在集合中。如果是，则忽略该数字，否则继续使用与之前相同的方法。或者，可以颠倒操作的顺序：首先删除，然后插入。下面的代码实现了这种行为：
set<int> st;
set<int>::iterator it;
st.clear();
for(int i=0; i<n; i++) {
it = st.lower_bound(a[i]);
if (it != st.end()) st.erase(it);
st.insert(a[i]);
}
cout<<st.size()<<endl;
第二种算法可以通过维护一个包含 LIS 的前一个元素在原始数组中的位置的父数组来扩展以找到最长的递增子序列 (LIS) 本身。
typedef pair<int, int> IndexValue;
struct IndexValueCompare{
inline bool operator() (const IndexValue &one, const IndexValue &another){
return one.second < another.second;
}
};
vector<int> LIS(const vector<int> &sequence){
vector<int> parent(sequence.size());
set<IndexValue, IndexValueCompare> s;
for(int i = 0; i < sequence.size(); ++i){
IndexValue iv(i, sequence[i]);
if(i == 0){
s.insert(iv);
continue;
}
auto index = s.lower_bound(iv);
if(index != s.end()){
if(sequence[i] < sequence[index->first]){
if(index != s.begin()) {
parent[i] = (--index)->first;
index++;
}
s.erase(index);
}
} else{
parent[i] = s.rbegin()->first;
}
s.insert(iv);
}
vector<int> result(s.size());
int index = s.rbegin()->first;
for(auto iter = s.rbegin(); iter != s.rend(); index = parent[index], ++iter){
result[distance(iter, s.rend()) - 1] = sequence[index];
}
return result;
}
于 2012-09-29T23:03:29.927 回答
13
我们需要维护递增序列的列表。
一般来说，我们有一组不同长度的活动列表。我们正在向这些列表中添加一个元素 A[i]。我们按长度递减的顺序扫描列表（寻找结束元素）。我们将验证所有列表的结束元素，以找到一个结束元素小于 A[i]（下限值）的列表。
我们的策略由以下条件确定，
1. 如果 A[i] 在所有活动列表的候选结束中最小，我们将开始新的长度为 1 的活动列表。
2. 如果 A[i] 在所有活动结束候选中最大列表，我们将克隆最大的活动列表，并将其扩展 A[i]。
3. 如果 A[i] 介于两者之间，我们将找到一个小于 A[i] 的最大末端元素的列表。克隆并通过 A[i] 扩展此列表。我们将丢弃与此修改后的列表长度相同的所有其他列表。
请注意，在我们构建活动列表的任何情况下，都会保持以下条件。
“较小列表的结束元素小于较大列表的结束元素”。
举个例子就清楚了，让我们以wiki为例：
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}。
A[0] = 0。案例 1。没有活动列表，创建一个。
0
.------------------------------------------------ -----------------------------------------
A[1] = 8。案例 2。克隆和扩展。
0.
0, 8.
------------------------------ ---------------------------------
A[2] = 4. 案例 3. 克隆、扩展和丢弃。
0.
0, 4.
0, 8. 丢弃
--------------------------------------------------- --------------------------------------------------
A[3] = 12. 案例 2. 克隆和延长。
0.
0, 4.
0, 4, 12.
-------------------------------------- ---------------------------------------
A[4] = 2. 案例 3. 克隆，扩展和丢弃。
0.
0, 2.
0, 4. 丢弃。
0、4、12
。-------------------------------------------- ---------------------------------
A[5] = 10. 案例 3. 克隆、扩展和丢弃。
0.
0, 2.
0, 2, 10.
0, 4, 12. 丢弃。
-------------------------------------------------- ---------------------------------------
A[6] = 6. 案例 3. 克隆、扩展和丢弃。
0.
0, 2.
0, 2, 6.
0, 2, 10. 丢弃。
-------------------------------------------------- ---------------------------------------
A[7] = 14. 案例 2. 克隆和扩展。
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
------------------------------ -----------------------------------------------------------
A[8] = 1。案例 3。克隆、扩展和丢弃。
0.
0, 1.
0, 2. 丢弃。
0, 2, 6.
0, 2, 6, 14.
---------------------------------- -----------------------------------------
A[9] = 9. 案例 3 . 克隆、扩展和丢弃。
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. 丢弃。
-------------------------------------------------- ---------------------------------------
A[10] = 5. 案例 3. 克隆、扩展和丢弃。
0.
0, 1.
0, 1, 5.
0, 2, 6. 丢弃。
0, 2, 6, 9.
------------------------------ -----------------------------------
A[11] = 13. 案例 2. 克隆和扩展。
0。
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
---------------------- -------------------------------------------------- -----
A[12] = 3。案例 3。克隆、扩展和丢弃。
0.
0, 1.
0, 1, 3.
0, 1, 5. 丢弃。
0、2、6、9。0、2、6、9、13 。--------------------------------
_ ---------------------------------------------
A[13] = 11.案例3.克隆、扩展和丢弃。
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. 丢弃。-------------------------------------------------- ---------------------------------------
A[14] = 7. 案例 3. 克隆、扩展和丢弃。
0。
0, 1.
0, 1, 3.
0, 1, 3, 7. 0, 2, 6, 9. 丢弃。
0、2、6、9、11
。---------------------------------------- ------------------------------------------------
A[15] = 15. 案例 2. 克隆和扩展。
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <-- LIS 列表
另外，确保我们保持了“较小列表的结束元素小于较大列表的结束元素”的条件。
这种算法称为耐心排序。
http://en.wikipedia.org/wiki/Patience_sorting
所以，从纸牌中挑选一套西装。从洗好的花色中找出最长的递增子序列。你永远不会忘记这种方法。
复杂度：O(NlogN)
资料来源：http ://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
于 2013-07-15T17:53:24.543 回答
1
这里有一个证明https://strncat.github.io/jekyll/update/2019/06/25/longest-increasing-subsequence.html
基本上不可能不是严格递增的子序列。证明是矛盾的：假设不是，那么我们有两种情况： 情况 1) 有某个元素 M[j] 结束两个长度为 j 和 j+某个数字的子序列。这是不可能的（链接中的证明）
案例 2）与案例 1 略有不同，但推理几乎相同。你怎么能有一个最小的数字结束两个不同长度的两个子序列？不可能。
于 2019-07-17T17:53:03.150 回答
1
You cannot understand, because the code in wikipedia is wrong(I strongly believe so). It is not only wrong but the variables are poorly named. But it allowed me to spend time to understand how it works :D.
Now after I read the patience-sort. I rewrote the algorithm. I also wrote the corrected binary search.
Patience sort is like Insertion sort
Like insertion sort, patience-sort finds appropriate place for the next item by doing binary search. The binary search is done on the card-piles built in sorted order. Let me assign a variable for the card-pile.(I am talking about playing cards because patience is a simplified card game).
//! card piles contain pile of cards, nth pile contains n cards.
int top_card_list[n+1];
for(int i = 0; i <= n; i++) {
top_card_list[i] = -1;
}
Now the top_card_list contains the top-card of the card pile of height n. Patience sort places the card in hand over the highest top-card that is smaller than it(or the opposite). For further sorting note, please refer to wikipedia page for patience sort.
3
* 7 2
-------------------------------------------------------------
Pile of cards above (top card is larger than lower cards)
(note that pile of card represents longest increasing subsequence too !)
Binary search on pile of cards
Now to find a number while we do dynamic programming for longest-increasing subsequence, we run an inner loop which is O(n).
for(int i = 1; i < n; i++) { // outer loop
for(int j = 0; j < i; j++) { // inner loop
if(arr[i] > arr[j]) {
if(memo_len[i] < (memo_len[j]+1)) {
// relaxation
memo_len[i] = memo_len[j]+1;
result = std::max(result,memo_len[i]);
pred[i] = j;
}
}
}
}
And the inner-loop is there to find the highest-top card that is smaller than our card in hand.
But we know that we can do it by binary search ! (exercise: prove the correctness) In that way we can do that in O(log (number of piles)) time. Now O(number of piles) = O(number of cards)(but number of card is 52, it should be O(1)!, just joking!). So the total application runs in O(n log n) time.
Here is the revised the DP with binary search.
for(int i = 1; i < n; i++) {
pile_height[i] = 1;
const int j = pile_search(top_card_list, arr, pile_len, arr[i]);
if(arr[i] > arr[j]) {
if(pile_height[i] < (pile_height[j]+1)) {
// relaxation
pile_height[i] = pile_height[j]+1;
result = std::max(result,pile_height[i]);
pile_len = std::max(pile_len,pile_height[i]);
}
}
if(-1 == top_card_list[pile_height[i]] || arr[top_card_list[pile_height[i]]] > arr[i]) {
top_card_list[pile_height[i]] = i; // top card on the pile is now i
}
}
Here is the correct pile search below. It is simply a binary search, but it finds the index of the top-card which is smaller than card in hand.
inline static int pile_search(const int*top_card_list, const vector<int>& arr, int pile_len, int strict_upper_limit) {
int start = 1,bound=pile_len;
while(start < bound) {
if(arr[top_card_list[bound]] < strict_upper_limit) {
return top_card_list[bound];
}
int mid = (start+bound)/2 + ((start+bound)&1);
if(arr[top_card_list[mid]] >= strict_upper_limit) {
// go lower
bound = mid-1;
} else {
start = mid;
}
}
return top_card_list[bound];
}
Notice that unlike wikipedia, it returns top_card_list[bound] (my fix). Also notice where the top_card_list[] is updated in the dp. This code is tested for the boundary cases. I hope it helps.
于 2018-10-09T02:24:04.590 回答
0
算法背后的基本思想是保持给定长度的 LIS 列表以最小的可能元素结尾。构建这样的序列
- 在已知的最后一个元素序列中查找直接前任（假设它的长度
k） - 尝试将当前元素附加到此序列并为
k+1长度构建新的更好的解决方案
因为在第一步中您搜索较小的值，然后 X[i] 新的解决方案（for k+1）将具有最后一个元素，然后是更短的序列。
我希望它会有所帮助。
于 2011-05-25T19:51:35.083 回答
0
我想出了这个
set<int> my_set;
set<int>::iterator it;
vector <int> out;
out.clear();
my_set.clear();
for(int i = 1; i <= n; i++) {
my_set.insert(a[i]);
it = my_set.find(a[i]);
it++;
if(it != my_set.end())
st.erase(it);
else
out.push_back(*it);
}
cout<< out.size();
于 2013-07-30T15:29:06.650 回答
0
您一定可以查看此视频以获取说明：
https://www.youtube.com/watch?v=nf3YG4CnTbg&feature=youtu.be
我的 nlogn approch 代码是：
int n;
cin>>n;//LENGTH OF ARRAY
vector<int>v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
vector<int>d(n+1,INT_MAX);//AUXILLARY ARRAY
for(int i=0;i<=n;i++){
*lower_bound(d.begin(),d.end(),v[i])=v[i];
}
for(int i=0;i<n;i++){
if(d[i]==INT_MAX){
cout<<i;//LENGTH OF LIS
exit(0);
}
}
于 2020-06-22T04:54:26.350 回答