我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。
当前回答
下面的c++实现还包括一些使用名为prev的数组构建实际最长递增子序列的代码。
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;
}
其他回答
这是另一个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
这是一个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中使用动态编程和记忆实现了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²)中解决。同样的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^2)算法的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)))
}
}