查找最长的递增序列
给定一个数字序列，你需要从给定的input中find一个最长的子序列（不是必须的）。
我发现这个链接（ 维基百科上最长的子序列 ），但需要更多的解释。
如果有人能帮我理解O（n log n）的实现，那真的很有帮助。 如果你能用一个例子来解释algorithm，那将会非常感激。
我也看到了其他的post，我不明白的是：对于i = 1,2，…，n，L = 0：对于最大的正数j≤L进行二元search，使得X [M [j]] <X [i]（或设置j = 0，如果没有这样的值存在）上面的语句，从哪里开始二分search？ 如何初始化M []，X []？
一个简单的问题是find最长的增长子序列的长度。 你可以专注于首先理解这个问题。 algorithm的唯一区别是它不使用P数组。
x是一个序列的input，所以它可以被初始化为：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随着algorithm运行而增加， m的初始值的数量也随之增加。
这是一个示例运行。 x [i] ，并且在每次迭代结束时给出m （但是使用序列的值而不是索引）。
在每个迭代中的search正在寻找放置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数组中来find。
检索最佳子序列：
P将最近子序列中的前一个元素（作为x的索引）存储在每个数字中，并随着algorithm的进展而更新。 例如，当我们处理8时，我们知道它是在0之后，所以在P中存储8在0之后的事实。 您可以像链接列表一样从最后一个数字向后工作，以获得整个序列。
所以对于每个数字我们知道它之前的数字。 要find以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]（最长的子序列）
MIT网站给出了这个问题的最好解释之一。 http://people.csail.mit.edu/bdean/6.046/dp/
我希望这会清除你所有的疑虑。
基于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(); }
}
下面是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; }
晚会之后，但这里有一个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; };
基于@fgb的回答，我用c ++实现了algorithm，以find最长的严格递增的子序列。 希望这会有所帮助。
M [i]是长度为i的序列的最后一个元素的索引，P [i]是序列中i的前一个元素的索引，用来打印整个序列。
main（）用于运行简单的testing用例：{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; }
我们可以像序列一样在两个二维数组中实现它
8 2 4 0 7 1 3 7 9
而LIS是0 – > 2 – > 4 – > 7 – > 8，这是什么algorithm
