最长递增子序列(O(nlogn))

Question

LIS：wikipedia

有一件事情我无法理解：

为什么 X[M[i]] 是一个非递减序列？

Answer 1

我们先看一下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;
   }
}

Answer 2

这是来自编程竞赛搭便车指南 （注意：此实现假设列表中没有重复项）：

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;
}

Answer 3

我们需要维护递增序列的列表。

一般来说，我们有一组不同长度的活动列表。我们将元素 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/

Answer 4

我想出了这个

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();

Answer 5

你无法理解，因为维基百科中的代码是错误的（我坚信是这样）。这不仅是错误的，而且变量的命名也很糟糕。但它让我花时间去理解它是如何工作的：D。

现在，在我阅读完耐心排序后。我重写了算法。我还编写了更正的二分搜索。

耐心排序就像插入排序

与插入排序类似，耐心排序通过二分查找为下一项找到合适的位置。二分查找是在按排序顺序构建的卡片堆上完成的。让我为牌堆分配一个变量。（我说的是玩纸牌，因为耐心是一种简化的纸牌游戏）。

//! 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;
}

现在，top_card_list 包含高度为 n 的卡片堆的顶部卡片。耐心排序将手中的牌放在比它小的最高的顶牌（或相反的牌）之上。进一步的排序说明，请参考维基百科页面耐心排序。

             3
  *   7      2                   
-------------------------------------------------------------
  Pile of cards above (top card is larger than lower cards)
 (note that pile of card represents longest increasing subsequence too !)

在一堆卡片上进行二分搜索

现在，为了在对最长递增子序列进行动态规划时找到一个数字，我们运行一个 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;
            }
        }
    }
 }

内循环是为了找到比我们手中的牌小的最高的牌。

但我们知道我们可以通过二分搜索来做到这一点！ （练习：证明正确性）这样我们就可以在 O(log (桩数)) 时间内完成。现在O(桩数) = O(牌数)（但是牌数是52，应该是O(1)！开玩笑！）。因此整个应用程序的运行时间为O(n log n)。

这是修改后的二分查找 DP。

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
    }
}

下面是正确的堆搜索。它只是简单的二分查找，但它找到了比手中的牌小的顶牌的索引。

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];
}

请注意，与维基百科不同，它返回 top_card_list[bound] （我的修复）。另请注意 top_card_list[] 在 dp 中的更新位置。该代码针对边界情况进行了测试。我希望它有帮助。

Answer 6

这里有一个证明 https://strncat .github.io/jekyll/update/2019/06/25/longest-increasing-subsequence.html

基本上不可能不是严格递增子序列。
证明是通过反证法：假设不是，那么我们有两种情况：
情况 1) 有某个元素 M[j] 结束两个长度为 j 和 j+某个数字的子序列。这是不可能的（链接中的证明）

案例 2）与案例 1 略有不同，但推理几乎相同。如何用最小的数结束两个不同长度的两个子序列？不可能。

Answer 7

算法背后的基本思想是保留给定长度的 LIS 列表，以最小可能元素结尾。构造这样的序列

1. 在已知的最后一个元素序列中查找直接前一个元素（假设其长度为 k）
2. 尝试将当前元素附加到该序列并为 k+1 构建新的更好的解决方案> length

因为在第一步中您搜索的值小于 X[i]，所以新的解决方案（对于 k+1）将具有最后一个元素大于较短的序列。

我希望它会有所帮助。

Answer 8

您一定可以查看此视频以获取解释：

https://www.youtube .com/watch?v=nf3YG4CnTbg&feature=youtu.be

我的 nlogn 方法代码是：

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);
    }
}