你得到一个数字序列，你需要从给定的输入中找到一个最长的递增子序列（不一定是连续的）。
我找到了这个链接（维基百科上最长的增加子序列），但需要更多解释。
如果有人可以帮助我理解 O(n log n) 的实现，那将非常有帮助。如果你能用一个例子来解释这个算法，那将非常感激。
我也看到了其他帖子，但我不明白的是：L = 0 for i = 1, 2, ... n: 二分查找最大正数 j ≤ L 使得 X[M[j]] < X [i] （如果不存在这样的值，则设置 j = 0）上面的语句，从哪里开始二分查找？如何初始化 M[]、X[]？
一个更简单的问题是找到最长递增子序列的长度。你可以先专注于理解这个问题。该算法的唯一区别是它不使用P数组。
x是一个序列的输入，所以可以初始化为：x = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
m跟踪迄今为止找到的每个长度的最佳子序列。最好的是具有最小结束值的那个（允许在其后添加更广泛的值）。长度和结束值是每个子序列需要存储的唯一数据。
m的每个元素代表一个子序列。对于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]（最长的递增子序列）
麻省理工学院网站给出了对这个问题的最佳解释之一。 http://people.csail.mit.edu/bdean/6.046/dp/
我希望它能消除你所有的疑惑。
下面是 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;
}
基于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();
}
}
根据@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;
}
派对迟到了，但这里有一个 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;
};
O(N lg N)解来自纸牌的耐心排序。我从我的代码注释中找到了这一点，因此在这里分享。我相信每个人都更容易理解它是如何工作的。如果你理解得很好，你也可以找到所有可能的最长递增子序列列表。
代码：
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;
}