用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();
    }
}

下面是从动态规划的角度评估问题的三个步骤:

递归定义:maxLength(i) == 1 + maxLength(j) where 0 < j < i and array[i] > array[j] 递归参数边界:可能有0到i - 1个子序列作为参数传递 求值顺序:由于是递增子序列，所以要从0求值到n

如果我们以序列{0,8,2,3,7,9}为例，at index:

我们会得到子序列{0}作为基本情况 [1]有一个新的子序列{0,8} [2]试图评估两个新的序列{0,8,2}和{0,2}通过添加元素在索引2到现有的子序列-只有一个是有效的，所以添加第三个可能的序列{0,2}只到参数列表 .．.

下面是c++ 11的工作代码:

#include <iostream>
#include <vector>

int getLongestIncSub(const std::vector<int> &sequence, size_t index, std::vector<std::vector<int>> &sub) {
    if(index == 0) {
        sub.push_back(std::vector<int>{sequence[0]});
        return 1;
    }

    size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub);
    std::vector<std::vector<int>> tmpSubSeq;
    for(std::vector<int> &subSeq : sub) {
        if(subSeq[subSeq.size() - 1] < sequence[index]) {
            std::vector<int> newSeq(subSeq);
            newSeq.push_back(sequence[index]);
            longestSubSeq = std::max(longestSubSeq, newSeq.size());
            tmpSubSeq.push_back(newSeq);
        }
    }
    std::copy(tmpSubSeq.begin(), tmpSubSeq.end(),
              std::back_insert_iterator<std::vector<std::vector<int>>>(sub));

    return longestSubSeq;
}

int getLongestIncSub(const std::vector<int> &sequence) {
    std::vector<std::vector<int>> sub;
    return getLongestIncSub(sequence, sequence.size() - 1, sub);
}

int main()
{
    std::vector<int> seq{0, 8, 2, 3, 7, 9};
    std::cout << getLongestIncSub(seq);
    return 0;
}

这里是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中使用动态编程和记忆实现了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

说到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]
}

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²)时间内解决)但这种方法仍然提供了动态规划方法，这也是很好的。