我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。


当前回答

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 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

用Java签出包含数组元素的最长递增子序列的代码

http://ideone.com/Nd2eba

/**
 **    Java Program to implement Longest Increasing Subsequence Algorithm
 **/

import java.util.Scanner;

/** Class  LongestIncreasingSubsequence **/
 class  LongestIncreasingSubsequence
{
    /** function lis **/
    public int[] lis(int[] X)
    {        
        int n = X.length - 1;
        int[] M = new int[n + 1];  
        int[] P = new int[n + 1]; 
        int L = 0;

        for (int i = 1; i < n + 1; i++)
        {
            int j = 0;

            /** Linear search applied here. Binary Search can be applied too.
                binary search for the largest positive j <= L such that 
                X[M[j]] < X[i] (or set j = 0 if no such value exists) **/

            for (int pos = L ; pos >= 1; pos--)
            {
                if (X[M[pos]] < X[i])
                {
                    j = pos;
                    break;
                }
            }            
            P[i] = M[j];
            if (j == L || X[i] < X[M[j + 1]])
            {
                M[j + 1] = i;
                L = Math.max(L,j + 1);
            }
        }

        /** backtrack **/

        int[] result = new int[L];
        int pos = M[L];
        for (int i = L - 1; i >= 0; i--)
        {
            result[i] = X[pos];
            pos = P[pos];
        }
        return result;             
    }

    /** Main Function **/
    public static void main(String[] args) 
    {    
        Scanner scan = new Scanner(System.in);
        System.out.println("Longest Increasing Subsequence Algorithm Test\n");

        System.out.println("Enter number of elements");
        int n = scan.nextInt();
        int[] arr = new int[n + 1];
        System.out.println("\nEnter "+ n +" elements");
        for (int i = 1; i <= n; i++)
            arr[i] = scan.nextInt();

        LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence(); 
        int[] result = obj.lis(arr);       

        /** print result **/ 

        System.out.print("\nLongest Increasing Subsequence : ");
        for (int i = 0; i < result.length; i++)
            System.out.print(result[i] +" ");
        System.out.println();
    }
}

这是我的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)

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实现。不需要递归/记忆来生成实际的子序列。只是一个字符串数组,存储每个阶段的实际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