找到最长的递增序列

Question

给定一个数字序列，您需要从给定的输入中找到最长的递增子序列（不一定是连续的）。

我找到了此链接（维基百科上的最长递增子序列），但需要更多解释。

如果有人可以帮助我理解 O(n log n) 实现，那将非常有帮助。如果您能用一个例子解释该算法，我们将不胜感激。

我也看到了其他帖子，但我不明白的是： L = 0 对于 i = 1, 2, ... n： 二分查找最大正 j ≤ L 使得 X[M[j]] < X[i]（如果不存在这样的值，则设置 j = 0） 上面的语句，从哪里开始二分查找呢？如何初始化M[]、X[]？

Answer 1

一个更简单的问题是找到最长递增子序列的长度。您可以先专注于理解该问题。该算法的唯一区别是它不使用 P 数组。

x 是序列的输入，因此可以将其初始化为：
x = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

m 跟踪最佳子序列到目前为止找到的每个长度。最好的是最终值最小的那个（允许在其后添加更广泛的值）。长度和结束值是每个子序列需要存储的唯一数据。

m 的每个元素代表一个子序列。对于m[j]，

• j是子序列的长度。
• m[j] 是子序列最后一个元素的索引（以 x 为单位）。
• 因此，x[m[j]] 是子序列最后一个元素的值。

L是迄今为止找到的最长子序列的长度。 m 的前 L 值有效，其余未初始化。 m 可以从第一个元素为 0 开始，其余元素未初始化。 L 随着算法的运行而增加，m 的初始化值的数量也随之增加。

这是一个运行示例。给出每次迭代结束时的 x[i] 和 m （但使用序列的值而不是索引）。

每次迭代中的搜索都会寻找放置 x[i] 的位置。它应该尽可能向右（以获得最长的序列），并且大于其左侧的值（因此它是一个递增序列）。

 0:  m = [0, 0]        - ([0] is a subsequence of length 1.)
 8:  m = [0, 0, 8]     - (8 can be added after [0] to get a sequence of length 2.)
 4:  m = [0, 0, 4]     - (4 is better than 8. This can be added after [0] instead.)
 12: m = [0, 0, 4, 12] - (12 can be added after [...4])
 2:  m = [0, 0, 2, 12] - (2 can be added after [0] instead of 4.)
 10: m = [0, 0, 2, 10]
 6:  m = [0, 0, 2, 6]
 14: m = [0, 0, 2, 6, 14]
 1:  m = [0, 0, 1, 6, 14]
 9:  m = [0, 0, 1, 6, 9]
 5:  m = [0, 0, 1, 5, 9]
 13: m = [0, 0, 1, 5, 9, 13]
 3:  m = [0, 0, 1, 3, 9, 13]
 11: m = [0, 0, 1, 3, 9, 11]
 7:  m = [0, 0, 1, 3, 7, 11]
 15: m = [0, 0, 1, 3, 7, 11, 15]

现在我们知道有一个长度为 6、以 15 结尾的子序列。子序列中的实际值可以通过在循环期间将它们存储在 P 数组中来找到。

检索最佳子序列：

P 为每个数字存储最长子序列中的前一个元素（作为 x 的索引），并随着算法的进展进行更新。例如，当我们处理8时，我们知道它在0之后，因此将8在0之后的事实存储在P中。您可以像链表一样从最后一个数字向后推算以获得整个序列。

因此，对于每个数字，我们都知道它之前的数字。为了找到以 7 结尾的子序列，我们查看 P 并看到：

7 is after 3
3 is after 1
1 is after 0

所以我们有子序列 [0, 1, 3, 7]。

以 7 或 15 结尾的子序列共享一些数字：

15 is after 11
11 is after 9
9 is after 6
6 is after 2
2 is after 0

因此我们有子序列 [0, 2, 6, 9, 11] 和 [0, 2, 6, 9, 11, 15]（最长递增子序列）

Answer 2

麻省理工学院网站给出了对此问题的最佳解释之一。
http://people.csail.mit.edu/bdean/6.046/dp/

我希望它能消除您所有的疑虑。

Answer 3

基于FJB的回答，java实现：

public class Lis {

private static int[] findLis(int[] arr) {
    int[] is = new int[arr.length];
    int index = 0;
    is[0] = index;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[is[index]]) {
            for (int j = 0; j <= index; j++) {
                if (arr[i] < arr[is[j]]) {
                    is[j] = i;
                    break;
                }
            }
        } else if (arr[i] == arr[is[index]]) {

        } else {
            is[++index] = i;
        }
    }

    int[] lis = new int[index + 1];
    lis[index] = arr[is[index]];

    for (int i = index - 1; i >= 0; i--) {
        if (is[i] < is[i + 1]) {
            lis[i] = arr[is[i]];
        } else {
            for (int j = is[i + 1] - 1; j >= 0; j--) {
                if (arr[j] > arr[is[i]] && arr[j] < arr[is[i + 1]]) {
                    lis[i] = arr[j];
                    is[i] = j;
                    break;
                }
            }
        }
    }

    return lis;
}

public static void main(String[] args) {
    int[] arr = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11,
            7, 15 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();

    arr = new int[] { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();
}

}

Answer 4

下面是 O(NLogN) 最长递增子序列的实现：

// search for the index which can be replaced by the X. as the index can't be
//0 or end (because if 0 then replace in the findLIS() and if it's greater than the 
//current maximum the just append)of the array "result" so most of the boundary 
//conditions are not required.
public static int search(int[] result, int p, int r, int x)
{
    if(p > r) return -1;
    int q = (p+r)/2;
    if(result[q] < x && result[q+1]>x)
    {
        return q+1;
    }
    else if(result[q] > x)
    {
        return search(result, p, q, x);
    }
    else
    {
        return search(result, q+1, r, x);
    }
}
    public static int findLIS(int[] a)
    {
        int[] result = new int[a.length];
        result[0] = a[0];
        int index = 0;
        for(int i=1; i<a.length; i++)
        {
            int no = a[i];
            if(no < result[0]) // replacing the min number
            {
                result[0] = no;
            }
            else if(no > result[index])//if the number is bigger then the current big then append
            {
                result[++index] = no;
            }
            else
            {
                int c = search(result, 0, index, no);
                result[c] = no;
            }
        }
        return index+1;
    }

Answer 5

虽然迟到了，但这里有一个 JavaScript 实现可以与其他实现一起使用..:)

var findLongestSubsequence = function(array) {
  var longestPartialSubsequences = [];
  var longestSubsequenceOverAll = [];

  for (var i = 0; i < array.length; i++) {
    var valueAtI = array[i];
    var subsequenceEndingAtI = [];

    for (var j = 0; j < i; j++) {
      var subsequenceEndingAtJ = longestPartialSubsequences[j];
      var valueAtJ = array[j];

      if (valueAtJ < valueAtI && subsequenceEndingAtJ.length > subsequenceEndingAtI.length) {
        subsequenceEndingAtI = subsequenceEndingAtJ;
      }
    }

    longestPartialSubsequences[i] = subsequenceEndingAtI.concat();
    longestPartialSubsequences[i].push(valueAtI);

    if (longestPartialSubsequences[i].length > longestSubsequenceOverAll.length) {
      longestSubsequenceOverAll = longestPartialSubsequences[i];
    }
  }

  return longestSubsequenceOverAll;
};

Answer 6

根据@fgb的回答，我使用c++实现了算法来查找最长的严格递增子序列。希望这会有所帮助。

M[i]是长度为i的序列的最后一个元素的索引，P[i]是序列中i的前一个元素的索引，用于打印整个序列。

main() 用于运行简单的测试用例：{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}。

#include <vector>
using std::vector;
int LIS(const vector<int> &v) {
  int size = v.size(), max_len = 1;
  // M[i] is the index of the last element of the sequence whose length is i
  int *M = new int[size];
  // P[i] is the index of the previous element of i in the sequence, which is used to print the whole sequence
  int *P = new int[size];
  M[0] = 0; P[0] = -1;
  for (int i = 1; i < size; ++i) {
    if (v[i] > v[M[max_len - 1]]) {
      M[max_len] = i;
      P[i] = M[max_len - 1];
      ++max_len;
      continue;
    }
    // Find the position to insert i using binary search
    int lo = 0, hi = max_len - 1;
    while (lo <= hi) {
      int mid = lo + ((hi - lo) >> 1);
      if (v[i] < v[M[mid]]) {
        hi = mid - 1;
      } else if (v[i] > v[M[mid]]) {
        lo = mid + 1;
      } else {
        lo = mid;
        break;
      }
    }
    P[i] = P[M[lo]];  // Modify the previous pointer
    M[lo] = i;  
  }
  // Print the whole subsequence
  int i = M[max_len - 1];
  while (i >= 0) {
    printf("%d ", v[i]);
    i = P[i];
  }
  printf("\n");
  delete[] M, delete[] P;
  return max_len;
}
int main(int argc, char* argv[]) {
  int data[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
  vector<int> v;
  v.insert(v.end(), data, data + sizeof(data) / sizeof(int));
  LIS(v);
  return 0;
}

Answer 7

O(N lg N)的解决方案来自于扑克牌的耐心排序。我从我的代码注释中发现了这一点，因此在这里分享。我相信大家会更容易理解它是如何工作的。如果你理解得好的话，你还可以找到所有可能的最长递增子序列列表。

https://www.cs.princeton.edu/ course/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf

代码：

vector<int> lisNlgN(vector<int> v) {
    int n = v.size();
    vector<int> piles = vector<int>(n, INT_MAX);
    int maxLen = 0;

    for(int i = 0; i < n; i++) {
        int pos = lower_bound(piles.begin(), piles.end(), v[i]) - piles.begin();
        piles[pos] = v[i];
        maxLen = max(maxLen, pos+1); // Plus 1 because of 0-based index.
    }

//    // Print piles for debug purpose
//    for (auto x : piles) cout << x << " ";
//    cout << endl;
//
//    // Print position for debug purpose
//    for (auto x : position) cout << x << " ";
//    cout << endl;

    vector<int> ret = vector<int>(piles.begin(), piles.begin() + maxLen);
    return ret;
}

代码：

vector<vector<int>> allPossibleLIS(vector<int> v) {
    struct Card {
        int val;
        Card* parent = NULL;
        Card(int val) {
            this->val = val;
        }
    };
    auto comp = [](Card* a, Card* b) {
        return a->val < b->val;
    };

    int n = v.size();
    // Convert integers into card node
    vector<Card*> cards = vector<Card*>(n);
    for (int i = 0; i < n; i++) cards[i] = new Card(v[i]);
    vector<Card*> piles = vector<Card*>(n, new Card(INT_MAX));
    vector<Card*> lastPileCards;
    int maxLen = 0;

    for(int i = 0; i < n; i++) {
        int pos = lower_bound(piles.begin(), piles.end(), new Card(v[i]), comp) - piles.begin();
        piles[pos] = cards[i];

        // Link to top card of left pile
        if (pos == 0) cards[i]->parent = NULL;
        else cards[i]->parent = piles[pos-1];

        // Plus 1 because of 0-based index.
        if (pos+1 == maxLen) {
            lastPileCards.push_back(cards[i]);
        } else if (pos+1 > maxLen) {
            lastPileCards.clear();
            lastPileCards.push_back(cards[i]);
            maxLen = pos + 1;
        }
    }

//    Print for debug purpose
//    printf("maxLen = %d\n", maxLen);
//    printf("Total unique lis list = %d\n", lastPileCards.size());

    vector<vector<int>> ret;
    for (auto card : lastPileCards) {
        vector<int> lis;
        Card* c = card;
        while (c != NULL) {
            lis.push_back(c->val);
            c = c->parent;
        }
        reverse(lis.begin(), lis.end());
        ret.push_back(lis);
    }

    return ret;
}

Answer 8

我强烈建议点击此处更详细的解释。我还使用此链接进行以下解释。

该解决方案的总体思路是模仿耐心排序的过程来找到最长的长度递增子序列 (LIS)：

1. 构造一个列表，尾部。该列表将存储每堆最上面的牌。

2. 循环遍历 nums 列表中的每个元素。

3. 对于每个元素 x，根据以下规则更新 tails 列表：

   (1) 如果 x 大于 tails 中的所有元素，则将其追加。
   (2) 如果tails[i-1] x <= tails[i]，用 x 更新 tails[i]。

   这一步找到每个阶段的最佳最长递增子序列。

   请注意，此步骤是使用二分搜索完成的，因为我们可以使用二分搜索来循环 tails 并找到元素 x 的适当位置。

4. tails 列表是最长递增子序列。要查找所有子序列，我们只需在每次迭代时存储尾部列表即可。

例如，如果我们有 nums = [4,5,6,3]，那么 tails 列表会像这样增加：

[4]
[4, 5]
[4, 5, 6]
[3, 5, 6]

总的来说，我们已经迭代了 nums 一次，对于每个元素我们都使用过一次二分查找，因此大 O 将为 O(nlogn)。