我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。
当前回答
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²)时间内解决)但这种方法仍然提供了动态规划方法，这也是很好的。
其他回答
这是我的Leetcode解决方案使用二进制搜索:->
class Solution:
def binary_search(self,s,x):
low=0
high=len(s)-1
flag=1
while low<=high:
mid=(high+low)//2
if s[mid]==x:
flag=0
break
elif s[mid]<x:
low=mid+1
else:
high=mid-1
if flag:
s[low]=x
return s
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
s=[]
s.append(nums[0])
for i in range(1,len(nums)):
if s[-1]<nums[i]:
s.append(nums[i])
else:
s=self.binary_search(s,nums[i])
return len(s)
好的，我先描述最简单的解也就是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^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)))
}
}
最长递增子序列(Java)
import java.util.*;
class ChainHighestValue implements Comparable<ChainHighestValue>{
int highestValue;
int chainLength;
ChainHighestValue(int highestValue,int chainLength) {
this.highestValue = highestValue;
this.chainLength = chainLength;
}
@Override
public int compareTo(ChainHighestValue o) {
return this.chainLength-o.chainLength;
}
}
public class LongestIncreasingSubsequenceLinkedList {
private static LinkedList<Integer> LongestSubsequent(int arr[], int size){
ArrayList<LinkedList<Integer>> seqList=new ArrayList<>();
ArrayList<ChainHighestValue> valuePairs=new ArrayList<>();
for(int i=0;i<size;i++){
int currValue=arr[i];
if(valuePairs.size()==0){
LinkedList<Integer> aList=new LinkedList<>();
aList.add(arr[i]);
seqList.add(aList);
valuePairs.add(new ChainHighestValue(arr[i],1));
}else{
try{
ChainHighestValue heighestIndex=valuePairs.stream().filter(e->e.highestValue<currValue).max(ChainHighestValue::compareTo).get();
int index=valuePairs.indexOf(heighestIndex);
seqList.get(index).add(arr[i]);
heighestIndex.highestValue=arr[i];
heighestIndex.chainLength+=1;
}catch (Exception e){
LinkedList<Integer> aList=new LinkedList<>();
aList.add(arr[i]);
seqList.add(aList);
valuePairs.add(new ChainHighestValue(arr[i],1));
}
}
}
ChainHighestValue heighestIndex=valuePairs.stream().max(ChainHighestValue::compareTo).get();
int index=valuePairs.indexOf(heighestIndex);
return seqList.get(index);
}
public static void main(String[] args){
int arry[]={5,1,3,6,11,30,32,5,3,73,79};
//int arryB[]={3,1,5,2,6,4,9};
LinkedList<Integer> LIS=LongestSubsequent(arry, arry.length);
System.out.println("Longest Incrementing Subsequence:");
for(Integer a: LIS){
System.out.print(a+" ");
}
}
}
说到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]
}
