我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。
当前回答
c++中最简单的LIS解决方案，具有O(nlog(n))时间复杂度
#include <iostream>
#include "vector"
using namespace std;
// binary search (If value not found then it will return the index where the value should be inserted)
int ceilBinarySearch(vector<int> &a,int beg,int end,int value)
{
if(beg<=end)
{
int mid = (beg+end)/2;
if(a[mid] == value)
return mid;
else if(value < a[mid])
return ceilBinarySearch(a,beg,mid-1,value);
else
return ceilBinarySearch(a,mid+1,end,value);
return 0;
}
return beg;
}
int lis(vector<int> arr)
{
vector<int> dp(arr.size(),0);
int len = 0;
for(int i = 0;i<arr.size();i++)
{
int j = ceilBinarySearch(dp,0,len-1,arr[i]);
dp[j] = arr[i];
if(j == len)
len++;
}
return len;
}
int main()
{
vector<int> arr {2, 5,-1,0,6,1,2};
cout<<lis(arr);
return 0;
}
输出: 4
其他回答
这是一个O(n²)的Java实现。我只是没有使用二分搜索来找到S中最小的元素，它是>= than x，我只是使用了一个for循环。使用二分搜索将使复杂度为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));
}
用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();
}
}
好的，我先描述最简单的解也就是O(N²)N是集合的大小。还有一个O(N log N)解，我也会讲到。在高效算法一节中可以找到。
我假设数组的下标从0到N - 1。因此，让我们定义DP[i]为LIS(最长递增子序列)的长度，它结束于索引为i的元素。为了计算DP[i]，我们查看所有索引j < i，并检查DP[j] + 1 > DP[i]和array[j] < array[i](我们希望它是递增的)。如果这是真的，我们可以更新DP[i]的当前最优值。要找到数组的全局最优值，您可以从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是为了以后能够找到实际的序列，而不仅仅是它的长度。只需在循环中使用prev[bestEnd]从bestEnd递归返回。-1值是停止的标志。
好了，现在来看更有效的O(nlog N)解:
设S[pos]定义为长度为pos的递增序列结束的最小整数。现在遍历输入集的每个整数X，并执行以下操作:
如果X >是S中的最后一个元素，那么将X附加到S的末尾，这本质上意味着我们已经找到了一个新的最大的LIS。 否则，找到S中最小的元素，即>= X，并将其改为X。 因为S在任何时候都是排序的，所以可以使用log(N)的二分搜索来找到元素。
总运行时间- N个整数，并对每个整数进行二进制搜索- 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的大小)。
为了重建实际的LIS，我们将再次使用父数组。 设parent[i]是LIS中索引为i的元素的前身，该元素以索引为i的元素结束。
为了使事情更简单，我们可以在数组S中保留不是实际的整数，而是它们在集合中的下标(位置)。我们不保留{1,2,4,5,8}，而是保留{4,5,3,7,8}。
即输入[4]= 1，输入[5]= 2，输入[3]= 4，输入[7]= 5，输入[8]= 8。
如果我们正确地更新父数组，实际的LIS是:
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
现在重要的是，我们如何更新父数组?有两种选择:
如果X >是S中的最后一个元素，那么parent[indexX] = indexLastElement。这意味着最新元素的父元素是最后一个元素。我们只是在S的末尾加上X。 否则，找到S中最小元素的索引>= than X，并将其更改为X。这里parent[indexX] = S[index - 1]。
说到DP solution，我发现很奇怪的是没有人提到LIS可以简化为LCS。你所需要做的就是对原始序列的副本进行排序，删除所有重复的副本，然后对它们进行LCS。在伪代码中是:
def LIS(S):
T = sort(S)
T = removeDuplicates(T)
return LCS(S, T)
以及用Go语言编写的完整实现。如果你不需要重构解，你就不需要维护整个n^2 DP矩阵。
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]
}
c++中最简单的LIS解决方案，具有O(nlog(n))时间复杂度
#include <iostream>
#include "vector"
using namespace std;
// binary search (If value not found then it will return the index where the value should be inserted)
int ceilBinarySearch(vector<int> &a,int beg,int end,int value)
{
if(beg<=end)
{
int mid = (beg+end)/2;
if(a[mid] == value)
return mid;
else if(value < a[mid])
return ceilBinarySearch(a,beg,mid-1,value);
else
return ceilBinarySearch(a,mid+1,end,value);
return 0;
}
return beg;
}
int lis(vector<int> arr)
{
vector<int> dp(arr.size(),0);
int len = 0;
for(int i = 0;i<arr.size();i++)
{
int j = ceilBinarySearch(dp,0,len-1,arr[i]);
dp[j] = arr[i];
if(j == len)
len++;
}
return len;
}
int main()
{
vector<int> arr {2, 5,-1,0,6,1,2};
cout<<lis(arr);
return 0;
}
输出: 4
