Как определить самую длинную возрастающую подпоследовательность с помощью динамического программирования?

Question

У меня есть набор целых чисел. Я хочу найти самую длинную возрастающую подпоследовательность этого набора, используя динамическое программирование.

Answer 1

Это можно решить в O (n ^ 2) с помощью динамического программирования.

Обработка элементов ввода по порядку и ведение списка кортежей для каждого элемента. Каждый кортеж (A, B) для элемента i будет обозначать: A = длина самой длинной увеличивающейся подпоследовательности, заканчивающейся в i, и B = индекс предшественника списка [i] в ​​самой длинной увеличивающейся подпоследовательности, заканчивающейся в списке [i ].

Начните с элемента 1, список кортежей для элемента 1 будет [(1,0)] для элемента i отсканируйте список 0..i и найдите список элементов [k] так, чтобы list [k]

В конце найдите все элементы с максимальным значением A (длина LIS, заканчивающимся на элементе) и вернитесь назад, используя кортежи, чтобы получить список.

Я поделился кодом для того же на http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799

Answer 2

извлечение кода в 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();
    }
}

Answer 3

Вот реализация Java (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);
    }    
}

Answer 4

Это реализация Java в O (n ^ 2). Я просто не использовал бинарный поиск, чтобы найти наименьший элемент в S, который>> чем 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));

}

Answer 5

Это может быть решено в O (n ^ 2) с помощью динамического программирования. Код 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.