如何使用dynamic规划确定最长的增长子序列？

我有一套整数。 我想使用dynamic编程来find该集合中时间最长的子序列 。

Answer 1

好吧，我将首先描述最简单的解决scheme是O（N ^ 2），其中N是集合的大小。 还有一个O（N log N）的解决scheme，我也会介绍。 在Efficientalgorithm部分查找这里 。

我将假定数组的索引是从0到N-1。所以我们定义DP[i]是以索引i结束的LIS（最长增加的子序列）的长度。 为了计算DP[i]我们看所有的指数j < i并且检查DP[j] + 1 > DP[i]和array[j] < array[i] （我们希望它是否增加）。 如果这是真的，我们可以更新DP[i]的当前最佳值。 要findarrays的全局最优值，可以从DP[0...N - 1]取最大值。

 int maxLength = 1, bestEnd = 0; DP[0] = 1; prev[0] = -1; for (int i = 1; i < N; i++) { DP[i] = 1; prev[i] = -1; for (int j = i - 1; j >= 0; j--) if (DP[j] + 1 > DP[i] && array[j] < array[i]) { DP[i] = DP[j] + 1; prev[i] = j; } if (DP[i] > maxLength) { bestEnd = i; maxLength = DP[i]; } } 

我使用数组prev以后能够find实际的序列不仅是它的长度。 只需从bestEndrecursion地bestEnd ，使用prev[bestEnd]循环。 -1值是一个停止的标志。

---

OK，现在到更高效的O(N log N)解决scheme：

令S[pos]被定义为结束pos长度递增序列的最小整数。 现在迭代input集合的每个整数X并执行以下操作：

1. 如果X > S最后一个元素，则将X附加到S的结尾。 这个本质意味着我们已经find了一个新的最大的LIS 。

2. 否则，findS最小的元素，它大于X ，并将其更改为X 由于S是随时sorting的，因此可以使用log(N)二进制search来查找元素。

总运行时间 – N整数和每个二进制search – N * log（N）= O（N log N）

现在让我们做一个真实的例子：

整数集合： 2 6 3 4 1 2 9 5 8

脚步：

 0. S = {} - Initialize S to the empty set 1. S = {2} - New largest LIS 2. S = {2, 6} - New largest LIS 3. S = {2, 3} - Changed 6 to 3 4. S = {2, 3, 4} - New largest LIS 5. S = {1, 3, 4} - Changed 2 to 1 6. S = {1, 2, 4} - Changed 3 to 2 7. S = {1, 2, 4, 9} - New largest LIS 8. S = {1, 2, 4, 5} - Changed 9 to 5 9. S = {1, 2, 4, 5, 8} - New largest LIS 

所以LIS的长度是5 （S的大小）。

为了重build实际的LIS我们将再次使用父数组。 让parent[i]成为索引为i的元素的前导元素，在索引为i的元素的索引元素结尾。

为了简单起见，我们可以保留在数组S ，而不是实际的整数，但是它们的索引（位置）在集合中。 我们不保留{1, 2, 4, 5, 8} ，但保留{4, 5, 3, 7, 8} 。

这是input[4] = 1 ，input[5] = 2 ，input[3] = 4 ，input[7] = 5 ，input[8] = 8 。

如果我们正确更新父数组，实际的LIS是：

 input[S[lastElementOfS]], input[parent[S[lastElementOfS]]], input[parent[parent[S[lastElementOfS]]]], ........................................ 

现在重要的是 – 我们如何更新父数组？ 有两个选项：

1. 如果X > S最后一个元素，则parent[indexX] = indexLastElement元素parent[indexX] = indexLastElement 。 这意味着最新元素的父元素是最后一个元素。 我们只是把X加到S的末尾。

2. 否则findS最小元素的索引，该元素大于X ，并将其更改为X 这里parent[indexX] = S[index - 1] 。

Answer 2

Petar Minchev的解释帮助我解决了一些问题，但是我很难parsing什么是一切，所以我做了一个Python的实现，其中包含了过多的描述性variables名和大量的注释。 我做了一个简单的recursion解决scheme，O（n ^ 2）解决scheme和O（n log n）解决scheme。

我希望它有助于清理algorithm！

recursion的解决scheme

 def recursive_solution(remaining_sequence, bigger_than=None): """Finds the longest increasing subsequence of remaining_sequence that is bigger than bigger_than and returns it. This solution is O(2^n).""" # Base case: nothing is remaining. if len(remaining_sequence) == 0: return remaining_sequence # Recursive case 1: exclude the current element and process the remaining. best_sequence = recursive_solution(remaining_sequence[1:], bigger_than) # Recursive case 2: include the current element if it's big enough. first = remaining_sequence[0] if (first > bigger_than) or (bigger_than is None): sequence_with = [first] + recursive_solution(remaining_sequence[1:], first) # Choose whichever of case 1 and case 2 were longer. if len(sequence_with) >= len(best_sequence): best_sequence = sequence_with return best_sequence 

O（n ^ 2）dynamic规划解决scheme

 def dynamic_programming_solution(sequence): """Finds the longest increasing subsequence in sequence using dynamic programming. This solution is O(n^2).""" longest_subsequence_ending_with = [] backreference_for_subsequence_ending_with = [] current_best_end = 0 for curr_elem in range(len(sequence)): # It's always possible to have a subsequence of length 1. longest_subsequence_ending_with.append(1) # If a subsequence is length 1, it doesn't have a backreference. backreference_for_subsequence_ending_with.append(None) for prev_elem in range(curr_elem): subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1) # If the prev_elem is smaller than the current elem (so it's increasing) # And if the longest subsequence from prev_elem would yield a better # subsequence for curr_elem. if ((sequence[prev_elem] < sequence[curr_elem]) and (subsequence_length_through_prev > longest_subsequence_ending_with[curr_elem])): # Set the candidate best subsequence at curr_elem to go through prev. longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev) backreference_for_subsequence_ending_with[curr_elem] = prev_elem # If the new end is the best, update the best. if (longest_subsequence_ending_with[curr_elem] > longest_subsequence_ending_with[current_best_end]): current_best_end = curr_elem # Output the overall best by following the backreferences. best_subsequence = [] current_backreference = current_best_end while current_backreference is not None: best_subsequence.append(sequence[current_backreference]) current_backreference = (backreference_for_subsequence_ending_with[current_backreference]) best_subsequence.reverse() return best_subsequence 

O（n log n）dynamic规划解决scheme

 def find_smallest_elem_as_big_as(sequence, subsequence, elem): """Returns the index of the smallest element in subsequence as big as sequence[elem]. sequence[elem] must not be larger than every element in subsequence. The elements in subsequence are indices in sequence. Uses binary search.""" low = 0 high = len(subsequence) - 1 while high > low: mid = (high + low) / 2 # If the current element is not as big as elem, throw out the low half of # sequence. if sequence[subsequence[mid]] < sequence[elem]: low = mid + 1 # If the current element is as big as elem, throw out everything bigger, but # keep the current element. else: high = mid return high def optimized_dynamic_programming_solution(sequence): """Finds the longest increasing subsequence in sequence using dynamic programming and binary search (per http://en.wikipedia.org/wiki/Longest_increasing_subsequence). This solution is O(n log n).""" # Both of these lists hold the indices of elements in sequence and not the # elements themselves. # This list will always be sorted. smallest_end_to_subsequence_of_length = [] # This array goes along with sequence (not # smallest_end_to_subsequence_of_length). Following the corresponding element # in this array repeatedly will generate the desired subsequence. parent = [None for _ in sequence] for elem in range(len(sequence)): # We're iterating through sequence in order, so if elem is bigger than the # end of longest current subsequence, we have a new longest increasing # subsequence. if (len(smallest_end_to_subsequence_of_length) == 0 or sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]): # If we are adding the first element, it has no parent. Otherwise, we # need to update the parent to be the previous biggest element. if len(smallest_end_to_subsequence_of_length) > 0: parent[elem] = smallest_end_to_subsequence_of_length[-1] smallest_end_to_subsequence_of_length.append(elem) else: # If we can't make a longer subsequence, we might be able to make a # subsequence of equal size to one of our earlier subsequences with a # smaller ending number (which makes it easier to find a later number that # is increasing). # Thus, we look for the smallest element in # smallest_end_to_subsequence_of_length that is at least as big as elem # and replace it with elem. # This preserves correctness because if there is a subsequence of length n # that ends with a number smaller than elem, we could add elem on to the # end of that subsequence to get a subsequence of length n+1. location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem) smallest_end_to_subsequence_of_length[location_to_replace] = elem # If we're replacing the first element, we don't need to update its parent # because a subsequence of length 1 has no parent. Otherwise, its parent # is the subsequence one shorter, which we just added onto. if location_to_replace != 0: parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1]) # Generate the longest increasing subsequence by backtracking through parent. curr_parent = smallest_end_to_subsequence_of_length[-1] longest_increasing_subsequence = [] while curr_parent is not None: longest_increasing_subsequence.append(sequence[curr_parent]) curr_parent = parent[curr_parent] longest_increasing_subsequence.reverse() return longest_increasing_subsequence 

Answer 3

谈到DP解决scheme，我感到奇怪的是，没有人提到LIS可以简化为LCS的事实。 所有你需要做的是sorting原始序列的副本，删除所有重复，并做他们的LCS。 伪代码是：

 def LIS(S): T = sort(S) T = removeDuplicates(T) return LCS(S, T) 

和完整的实现写在Go。 如果不需要重构解决scheme，则不需要维护整个n ^ 2 DPmatrix。

 func lcs(arr1 []int) int { arr2 := make([]int, len(arr1)) for i, v := range arr1 { arr2[i] = v } sort.Ints(arr1) arr3 := []int{} prev := arr1[0] - 1 for _, v := range arr1 { if v != prev { prev = v arr3 = append(arr3, v) } } n1, n2 := len(arr1), len(arr3) M := make([][]int, n2 + 1) e := make([]int, (n1 + 1) * (n2 + 1)) for i := range M { M[i] = e[i * (n1 + 1):(i + 1) * (n1 + 1)] } for i := 1; i <= n2; i++ { for j := 1; j <= n1; j++ { if arr2[j - 1] == arr3[i - 1] { M[i][j] = M[i - 1][j - 1] + 1 } else if M[i - 1][j] > M[i][j - 1] { M[i][j] = M[i - 1][j] } else { M[i][j] = M[i][j - 1] } } } return M[n2][n1] } 

Answer 4

下面的C ++实现还包含一些使用名为prev的数组构build实际的最长递增子序列的代码。

 std::vector<int> longest_increasing_subsequence (const std::vector<int>& s) { int best_end = 0; int sz = s.size(); if (!sz) return std::vector<int>(); std::vector<int> prev(sz,-1); std::vector<int> memo(sz, 0); int max_length = std::numeric_limits<int>::min(); memo[0] = 1; for ( auto i = 1; i < sz; ++i) { for ( auto j = 0; j < i; ++j) { if ( s[j] < s[i] && memo[i] < memo[j] + 1 ) { memo[i] = memo[j] + 1; prev[i] = j; } } if ( memo[i] > max_length ) { best_end = i; max_length = memo[i]; } } // Code that builds the longest increasing subsequence using "prev" std::vector<int> results; results.reserve(sz); std::stack<int> stk; int current = best_end; while (current != -1) { stk.push(s[current]); current = prev[current]; } while (!stk.empty()) { results.push_back(stk.top()); stk.pop(); } return results; } 

没有堆栈的实现只是反转向量

 #include <iostream> #include <vector> #include <limits> std::vector<int> LIS( const std::vector<int> &v ) { auto sz = v.size(); if(!sz) return v; std::vector<int> memo(sz, 0); std::vector<int> prev(sz, -1); memo[0] = 1; int best_end = 0; int max_length = std::numeric_limits<int>::min(); for (auto i = 1; i < sz; ++i) { for ( auto j = 0; j < i ; ++j) { if (s[j] < s[i] && memo[i] < memo[j] + 1) { memo[i] = memo[j] + 1; prev[i] = j; } } if(memo[i] > max_length) { best_end = i; max_length = memo[i]; } } // create results std::vector<int> results; results.reserve(v.size()); auto current = best_end; while (current != -1) { results.push_back(s[current]); current = prev[current]; } std::reverse(results.begin(), results.end()); return results; } 

Answer 5

以下是从dynamic编程的angular度评估问题的三个步骤：

1. 重复定义：maxLength（i）== 1 + maxLength（j）其中0 <j <i和array [i]> array [j]
2. 重复参数边界：可能有0到1 – 1个子序列作为parameter passing
3. 评估顺序：随着子序列的增加，必须从0到n进行评估

如果我们以序列{0,8,2,3,7,9}为例，索引为：

• [0]我们将得到子序列{0}作为基本情况
• [1]我们有一个新的子序列{0,8}
• [2]试图通过将索引2中的元素添加到现有子序列来评估两个新序列{0,8,2}和{0,2} – 只有一个是有效的，所以仅添加第三可能序列{0,2}到参数列表…

以下是正在运行的C ++ 11代码：

 #include <iostream> #include <vector> int getLongestIncSub(const std::vector<int> &sequence, size_t index, std::vector<std::vector<int>> &sub) { if(index == 0) { sub.push_back(std::vector<int>{sequence[0]}); return 1; } size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub); std::vector<std::vector<int>> tmpSubSeq; for(std::vector<int> &subSeq : sub) { if(subSeq[subSeq.size() - 1] < sequence[index]) { std::vector<int> newSeq(subSeq); newSeq.push_back(sequence[index]); longestSubSeq = std::max(longestSubSeq, newSeq.size()); tmpSubSeq.push_back(newSeq); } } std::copy(tmpSubSeq.begin(), tmpSubSeq.end(), std::back_insert_iterator<std::vector<std::vector<int>>>(sub)); return longestSubSeq; } int getLongestIncSub(const std::vector<int> &sequence) { std::vector<std::vector<int>> sub; return getLongestIncSub(sequence, sequence.size() - 1, sub); } int main() { std::vector<int> seq{0, 8, 2, 3, 7, 9}; std::cout << getLongestIncSub(seq); return 0; } 

Answer 6

这是O（n ^ 2）algorithm的一个Scala实现：

 object Solve { def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = { xs.foldLeft(List[(Int, List[T])]()) { (sofar, x) => if (sofar.isEmpty) List((1, List(x))) else { val resIfEndsAtCurr = (sofar, xs).zipped map { (tp, y) => val len = tp._1 val seq = tp._2 if (ord.lteq(y, x)) { (len + 1, x :: seq) // reversely recorded to avoid O(n) } else { (1, List(x)) } } sofar :+ resIfEndsAtCurr.maxBy(_._1) } }.maxBy(_._1)._2.reverse } def main(args: Array[String]) = { println(longestIncrSubseq(List( 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))) } } 

Answer 7

这是另一个O（n ^ 2）JAVA实现。 没有recursion/记忆生成实际的子序列。 只是一个string数组，存储每个阶段的实际LIS和一个数组来存储每个元素的LIS长度。 相当简单。 看一看：

 import java.io.BufferedReader; import java.io.InputStreamReader; /** * Created by Shreyans on 4/16/2015 */ class LNG_INC_SUB//Longest Increasing Subsequence { public static void main(String[] args) throws Exception { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter Numbers Separated by Spaces to find their LIS\n"); String[] s1=br.readLine().split(" "); int n=s1.length; int[] a=new int[n];//Array actual of Numbers String []ls=new String[n];// Array of Strings to maintain LIS for every element for(int i=0;i<n;i++) { a[i]=Integer.parseInt(s1[i]); } int[]dp=new int[n];//Storing length of max subseq. int max=dp[0]=1;//Defaults String seq=ls[0]=s1[0];//Defaults for(int i=1;i<n;i++) { dp[i]=1; String x=""; for(int j=i-1;j>=0;j--) { //First check if number at index j is less than num at i. // Second the length of that DP should be greater than dp[i] // -1 since dp of previous could also be one. So we compare the dp[i] as empty initially if(a[j]<a[i]&&dp[j]>dp[i]-1) { dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j] x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on } } x+=(" "+a[i]); ls[i]=x; if(dp[i]>max) { max=dp[i]; seq=ls[i]; } } System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq); } } 

行动代码： http ： //ideone.com/sBiOQx

Answer 8

这可以使用dynamic规划在O（n ^ 2）中解决。 相同的Python代码将如下所示： –

 def LIS(numlist): LS = [1] for i in range(1, len(numlist)): LS.append(1) for j in range(0, i): if numlist[i] > numlist[j] and LS[i]<=LS[j]: LS[i] = 1 + LS[j] print LS return max(LS) numlist = map(int, raw_input().split(' ')) print LIS(numlist) 

input： 5 19 5 81 50 28 29 1 83 23

输出将是： [1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5

输出列表的list_index是input列表的list_index。 输出列表中给定的list_index处的值表示该list_index的最长增加的子序列长度。

Answer 9

这里是java O（nlogn）的实现

 import java.util.Scanner; public class LongestIncreasingSeq { private static int binarySearch(int table[],int a,int len){ int end = len-1; int beg = 0; int mid = 0; int result = -1; while(beg <= end){ mid = (end + beg) / 2; if(table[mid] < a){ beg=mid+1; result = mid; }else if(table[mid] == a){ return len-1; }else{ end = mid-1; } } return result; } public static void main(String[] args) { // int[] t = {1, 2, 5,9,16}; // System.out.println(binarySearch(t , 9, 5)); Scanner in = new Scanner(System.in); int size = in.nextInt();//4; int A[] = new int[size]; int table[] = new int[A.length]; int k = 0; while(k<size){ A[k++] = in.nextInt(); if(k<size-1) in.nextLine(); } table[0] = A[0]; int len = 1; for (int i = 1; i < A.length; i++) { if(table[0] > A[i]){ table[0] = A[i]; }else if(table[len-1]<A[i]){ table[len++]=A[i]; }else{ table[binarySearch(table, A[i],len)+1] = A[i]; } } System.out.println(len); } } 

Answer 10

这是O（n ^ 2）中的一个Java实现。 我只是没有使用二进制search来findS中最小的元素，它大于X.我只是使用了一个for循环。 使用二进制search会使O（n logn）

 public static void olis(int[] seq){ int[] memo = new int[seq.length]; memo[0] = seq[0]; int pos = 0; for (int i=1; i<seq.length; i++){ int x = seq[i]; if (memo[pos] < x){ pos++; memo[pos] = x; } else { for(int j=0; j<=pos; j++){ if (memo[j] >= x){ memo[j] = x; break; } } } //just to print every step System.out.println(Arrays.toString(memo)); } //the final array with the LIS System.out.println(Arrays.toString(memo)); System.out.println("The length of lis is " + (pos + 1)); } 

Answer 11

使用数组元素在java中检出最长的子序列

http://ideone.com/Nd2eba

 /** ** Java Program to implement Longest Increasing Subsequence Algorithm **/ import java.util.Scanner; /** Class LongestIncreasingSubsequence **/ class LongestIncreasingSubsequence { /** function lis **/ public int[] lis(int[] X) { int n = X.length - 1; int[] M = new int[n + 1]; int[] P = new int[n + 1]; int L = 0; for (int i = 1; i < n + 1; i++) { int j = 0; /** Linear search applied here. Binary Search can be applied too. binary search for the largest positive j <= L such that X[M[j]] < X[i] (or set j = 0 if no such value exists) **/ for (int pos = L ; pos >= 1; pos--) { if (X[M[pos]] < X[i]) { j = pos; break; } } P[i] = M[j]; if (j == L || X[i] < X[M[j + 1]]) { M[j + 1] = i; L = Math.max(L,j + 1); } } /** backtrack **/ int[] result = new int[L]; int pos = M[L]; for (int i = L - 1; i >= 0; i--) { result[i] = X[pos]; pos = P[pos]; } return result; } /** Main Function **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Longest Increasing Subsequence Algorithm Test\n"); System.out.println("Enter number of elements"); int n = scan.nextInt(); int[] arr = new int[n + 1]; System.out.println("\nEnter "+ n +" elements"); for (int i = 1; i <= n; i++) arr[i] = scan.nextInt(); LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence(); int[] result = obj.lis(arr); /** print result **/ System.out.print("\nLongest Increasing Subsequence : "); for (int i = 0; i < result.length; i++) System.out.print(result[i] +" "); System.out.println(); } } 

Answer 12

这可以用O（n ^ 2）中的dynamic规划来解决。

按顺序处理input元素并维护每个元素的元组列表。 对于元素i，每个元组（A，B）将表示：A =在i处结束的最长增加子序列的长度，B =在列表[i中结束的最长增加子序列中列表[i]的前任索引]。

从元素1开始，元素1的元组列表将是[（1,0）]，扫描列表0..i并find元素列表[k]，使得列表[k] <list [i] ，元素i的A的值Ai将是Ak + 1，并且Bi将是k。 如果有多个这样的元素，将它们添加到元素i的元组列表中。

最后，find所有最大值为A的元素（LIS的长度以元素结尾），并使用元组回溯到列表中。

我在http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799上分享了相同的代码;

Answer 13

O（n ^ 2）java实现：

 void LIS(int arr[]){ int maxCount[]=new int[arr.length]; int link[]=new int[arr.length]; int maxI=0; link[0]=0; maxCount[0]=0; for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { if(arr[j]<arr[i] && ((maxCount[j]+1)>maxCount[i])){ maxCount[i]=maxCount[j]+1; link[i]=j; if(maxCount[i]>maxCount[maxI]){ maxI=i; } } } } for (int i = 0; i < link.length; i++) { System.out.println(arr[i]+" "+link[i]); } print(arr,maxI,link); } void print(int arr[],int index,int link[]){ if(link[index]==index){ System.out.println(arr[index]+" "); return; }else{ print(arr, link[index], link); System.out.println(arr[index]+" "); } }