我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。
当前回答
这可以用动态规划在O(n²)中解决。同样的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)
输入:5 19 5 81 50 28 29 1 83 23
输出将是:[1,2,1,3,3,3,4,1,5,3] 5
输出列表的list_index是输入列表的list_index。输出列表中给定list_index的值表示该list_index的最长递增子序列长度。
其他回答
这可以用动态规划在O(n²)中解决。同样的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)
输入:5 19 5 81 50 28 29 1 83 23
输出将是:[1,2,1,3,3,3,4,1,5,3] 5
输出列表的list_index是输入列表的list_index。输出列表中给定list_index的值表示该list_index的最长递增子序列长度。
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
我已经在java中使用动态编程和记忆实现了LIS。随着代码,我做了复杂性计算,即为什么它是O(n Log(base2) n)。因为我觉得理论或逻辑解释是很好的,但实际演示总是更好的理解。
package com.company.dynamicProgramming;
import java.util.HashMap;
import java.util.Map;
public class LongestIncreasingSequence {
static int complexity = 0;
public static void main(String ...args){
int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
int n = arr.length;
Map<Integer, Integer> memo = new HashMap<>();
lis(arr, n, memo);
//Display Code Begins
int x = 0;
System.out.format("Longest Increasing Sub-Sequence with size %S is -> ",memo.get(n));
for(Map.Entry e : memo.entrySet()){
if((Integer)e.getValue() > x){
System.out.print(arr[(Integer)e.getKey()-1] + " ");
x++;
}
}
System.out.format("%nAnd Time Complexity for Array size %S is just %S ", arr.length, complexity );
System.out.format( "%nWhich is equivalent to O(n Log n) i.e. %SLog(base2)%S is %S",arr.length,arr.length, arr.length * Math.ceil(Math.log(arr.length)/Math.log(2)));
//Display Code Ends
}
static int lis(int[] arr, int n, Map<Integer, Integer> memo){
if(n==1){
memo.put(1, 1);
return 1;
}
int lisAti;
int lisAtn = 1;
for(int i = 1; i < n; i++){
complexity++;
if(memo.get(i)!=null){
lisAti = memo.get(i);
}else {
lisAti = lis(arr, i, memo);
}
if(arr[i-1] < arr[n-1] && lisAti +1 > lisAtn){
lisAtn = lisAti +1;
}
}
memo.put(n, lisAtn);
return lisAtn;
}
}
当我运行上面的代码-
Longest Increasing Sub-Sequence with size 6 is -> 10 22 33 50 60 80
And Time Complexity for Array size 9 is just 36
Which is equivalent to O(n Log n) i.e. 9Log(base2)9 is 36.0
Process finished with exit code 0
这是一个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));
}
求最长递增子序列的O(NLog(N))方法 让我们维护一个数组,其中第i个元素是一个大小为i的子序列可以结束的最小的数字。
我故意避免进一步的细节,因为投票最多的答案已经解释了它,但这种技术最终导致使用set数据结构的整洁实现(至少在c++中)。
下面是c++中的实现(假设需要严格增加最长子序列的大小)
#include <bits/stdc++.h> // gcc supported header to include (almost) everything
using namespace std;
typedef long long ll;
int main()
{
ll n;
cin >> n;
ll arr[n];
set<ll> S;
for(ll i=0; i<n; i++)
{
cin >> arr[i];
auto it = S.lower_bound(arr[i]);
if(it != S.end())
S.erase(it);
S.insert(arr[i]);
}
cout << S.size() << endl; // Size of the set is the required answer
return 0;
}