我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。
当前回答
def longestincrsub(arr1):
n=len(arr1)
l=[1]*n
for i in range(0,n):
for j in range(0,i) :
if arr1[j]<arr1[i] and l[i]<l[j] + 1:
l[i] =l[j] + 1
l.sort()
return l[-1]
arr1=[10,22,9,33,21,50,41,60]
a=longestincrsub(arr1)
print(a)
尽管有一种方法可以在O(nlogn)时间内解决这个问题(它在O(n²)时间内解决)但这种方法仍然提供了动态规划方法，这也是很好的。
其他回答
好的，我先描述最简单的解也就是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]。
这可以用动态规划在O(n²)中解决。
按顺序处理输入元素，并为每个元素维护一个元组列表。每个元组(A,B)，对于i将表示的元素，A =以i结尾的最长递增子序列的长度，B =以列表[i]结尾的最长递增子序列中列表[i]的前身的索引。
从元素1开始，元素1的元组列表为[(1,0)] 对于元素i，扫描列表0..i，找到元素list[k]，使得list[k] < list[i]，元素i的A值，Ai为Ak + 1, Bi为k。如果有多个这样的元素，将它们添加到元素i的元组列表中。
最后，找到所有最大值为A (LIS以element结尾的长度)的元素，并使用元组回溯以获得列表。
我已经在http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799上分享了相同的代码
这是另一个O(n²)JAVA实现。不需要递归/记忆来生成实际的子序列。只是一个字符串数组，存储每个阶段的实际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
这里是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);
}
}
//可以使用TreeSet
O(n²)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]+" ");
}
}
