我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。
当前回答
下面是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)))
}
}
其他回答
下面是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)))
}
}
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));
}
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²)时间内解决)但这种方法仍然提供了动态规划方法,这也是很好的。
说到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]
}