wake-up-neo.com

Wie lässt sich die am längsten wachsende Teilsequenz durch dynamische Programmierung ermitteln?

Ich habe eine Reihe von ganzen Zahlen. Ich möchte die am längsten wachsende Teilsequenz dieser Gruppe durch dynamische Programmierung ermitteln.

191
Tony

OK, ich werde zuerst die einfachste Lösung beschreiben, die O (N ^ 2) ist, wobei N die Größe der Sammlung ist. Es gibt auch eine O (N log N) -Lösung, die ich auch beschreiben werde. Schauen Sie sich hier im Abschnitt Effiziente Algorithmen an.

Ich gehe davon aus, dass die Indizes des Arrays von 0 bis N - 1 reichen. Definieren wir also DP[i] als Länge der LIS (Longest zunehmende Untersequenz), die am Element mit dem Index i endet. Um DP[i] zu berechnen, betrachten wir alle Indizes j < i und prüfen, ob DP[j] + 1 > DP[i] und array[j] < array[i] (wir möchten, dass es ansteigt). Wenn dies zutrifft, können wir das aktuelle Optimum für DP[i] aktualisieren. Um das globale Optimum für das Array zu ermitteln, können Sie den Maximalwert von DP[0...N - 1] verwenden.

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];
   }
}

Ich benutze das Array prev, um später die tatsächliche Sequenz und nicht nur deren Länge zu finden. Gehen Sie einfach rekursiv von bestEnd in einer Schleife mit prev[bestEnd] zurück. Der -1-Wert ist ein Zeichen zum Anhalten.


OK, jetzt zur effizienteren O(N log N)-Lösung:

Sei S[pos] als kleinste Ganzzahl definiert, die eine aufsteigende Sequenz von Länge pos beendet. Jetzt durchlaufen Sie jede ganze Zahl X des Eingabesets und führen Sie folgende Schritte aus:

  1. Wenn X> letztes Element in S ist, hängen Sie X an das Ende von S an. Dies bedeutet, dass wir eine neue größte LIS gefunden haben.

  2. Suchen Sie andernfalls das kleinste Element in S, das >= als X ist, und ändern Sie es in X. Da S jederzeit sortiert ist, kann das Element mithilfe der binären Suche in log(N) gefunden werden.

Gesamtlaufzeit - N-Ganzzahlen und eine binäre Suche für jede davon - N * log (N) = O (N log N)

Lassen Sie uns nun ein reales Beispiel geben:

Auflistung ganzer Zahlen: 2 6 3 4 1 2 9 5 8

Schritte:

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

Die Länge des LIS ist also 5 (die Größe von S).

Um das eigentliche LIS zu rekonstruieren, verwenden wir wieder ein übergeordnetes Array . Der parent[i] sei der Vorgänger des Elements mit dem Index i im LIS, das mit dem Element i endet.

Zur Vereinfachung können wir im Array S nicht die eigentlichen Ganzzahlen, sondern deren Indizes (Positionen) im Satz behalten. Wir behalten nicht {1, 2, 4, 5, 8}, sondern {4, 5, 3, 7, 8}

Das ist Eingang [4] = 1, Eingang [5] = 2, Eingang [3] = 4, Eingang [7] = 5, Eingang [8] = 8.

Wenn wir das übergeordnete Array ordnungsgemäß aktualisieren, lautet das tatsächliche LIS:

input[S[lastElementOfS]], 
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................

Nun zur wichtigen Sache - wie aktualisieren wir das übergeordnete Array? Es gibt zwei Möglichkeiten:

  1. Wenn X> letztes Element in S ist, dann parent[indexX] = indexLastElement. Dies bedeutet, dass das übergeordnete Element des neuesten Elements das letzte Element ist. Wir legen nur X dem Ende von S voran.

  2. Suchen Sie andernfalls den Index des kleinsten Elements in S, das >= als X ist, und ändern Sie ihn in X. Hier parent[indexX] = S[index - 1].

363
Petar Minchev

Die Erklärung von Petar Minchev hat mir geholfen, die Dinge zu klären, aber es fiel mir schwer, zu analysieren, was alles war. Deshalb machte ich eine Python-Implementierung mit übermäßig beschreibenden Variablennamen und vielen Kommentaren. Ich habe eine naive rekursive Lösung gemacht, die O (n ^ 2) -Lösung und die O (n log n) -Lösung.

Ich hoffe, es hilft, die Algorithmen aufzuklären!

Die rekursive Lösung

def recursive_solution(remaining_sequence, bigger_than=None):
    """Finds the longest increasing subsequence of remaining_sequence that is      
    bigger than bigger_than and returns it.  This solution is O(2^n)."""

    # Base case: nothing is remaining.                                             
    if len(remaining_sequence) == 0:
        return remaining_sequence

    # Recursive case 1: exclude the current element and process the remaining.     
    best_sequence = recursive_solution(remaining_sequence[1:], bigger_than)

    # Recursive case 2: include the current element if it's big enough.            
    first = remaining_sequence[0]

    if (first > bigger_than) or (bigger_than is None):

        sequence_with = [first] + recursive_solution(remaining_sequence[1:], first)

        # Choose whichever of case 1 and case 2 were longer.                         
        if len(sequence_with) >= len(best_sequence):
            best_sequence = sequence_with

    return best_sequence                                                        

Die dynamische Programmierlösung von O (n ^ 2)

def dynamic_programming_solution(sequence):
    """Finds the longest increasing subsequence in sequence using dynamic          
    programming.  This solution is O(n^2)."""

    longest_subsequence_ending_with = []
    backreference_for_subsequence_ending_with = []
    current_best_end = 0

    for curr_elem in range(len(sequence)):
        # It's always possible to have a subsequence of length 1.                    
        longest_subsequence_ending_with.append(1)

        # If a subsequence is length 1, it doesn't have a backreference.             
        backreference_for_subsequence_ending_with.append(None)

        for prev_elem in range(curr_elem):
            subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1)

            # If the prev_elem is smaller than the current elem (so it's increasing)   
            # And if the longest subsequence from prev_elem would yield a better       
            # subsequence for curr_elem.                                               
            if ((sequence[prev_elem] < sequence[curr_elem]) and
                    (subsequence_length_through_prev >
                         longest_subsequence_ending_with[curr_elem])):

                # Set the candidate best subsequence at curr_elem to go through prev.    
                longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev)
                backreference_for_subsequence_ending_with[curr_elem] = prev_elem
                # If the new end is the best, update the best.    

        if (longest_subsequence_ending_with[curr_elem] >
                longest_subsequence_ending_with[current_best_end]):
            current_best_end = curr_elem
            # Output the overall best by following the backreferences.  

    best_subsequence = []
    current_backreference = current_best_end

    while current_backreference is not None:
        best_subsequence.append(sequence[current_backreference])
        current_backreference = (backreference_for_subsequence_ending_with[current_backreference])

    best_subsequence.reverse()

    return best_subsequence                                                   

Die dynamische Programmierlösung von O (n log n)

def find_smallest_elem_as_big_as(sequence, subsequence, elem):
    """Returns the index of the smallest element in subsequence as big as          
    sequence[elem].  sequence[elem] must not be larger than every element in       
    subsequence.  The elements in subsequence are indices in sequence.  Uses       
    binary search."""

    low = 0
    high = len(subsequence) - 1

    while high > low:
        mid = (high + low) / 2
        # If the current element is not as big as elem, throw out the low half of    
        # sequence.                                                                  
        if sequence[subsequence[mid]] < sequence[elem]:
            low = mid + 1
            # If the current element is as big as elem, throw out everything bigger, but 
        # keep the current element.                                                  
        else:
            high = mid

    return high


def optimized_dynamic_programming_solution(sequence):
    """Finds the longest increasing subsequence in sequence using dynamic          
    programming and binary search (per                                             
    http://en.wikipedia.org/wiki/Longest_increasing_subsequence).  This solution   
    is O(n log n)."""

    # Both of these lists hold the indices of elements in sequence and not the        
    # elements themselves.                                                         
    # This list will always be sorted.                                             
    smallest_end_to_subsequence_of_length = []

    # This array goes along with sequence (not                                     
    # smallest_end_to_subsequence_of_length).  Following the corresponding element 
    # in this array repeatedly will generate the desired subsequence.              
    parent = [None for _ in sequence]

    for elem in range(len(sequence)):
        # We're iterating through sequence in order, so if elem is bigger than the   
        # end of longest current subsequence, we have a new longest increasing          
        # subsequence.                                                               
        if (len(smallest_end_to_subsequence_of_length) == 0 or
                    sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]):
            # If we are adding the first element, it has no parent.  Otherwise, we        
            # need to update the parent to be the previous biggest element.            
            if len(smallest_end_to_subsequence_of_length) > 0:
                parent[elem] = smallest_end_to_subsequence_of_length[-1]
            smallest_end_to_subsequence_of_length.append(elem)
        else:
            # If we can't make a longer subsequence, we might be able to make a        
            # subsequence of equal size to one of our earlier subsequences with a         
            # smaller ending number (which makes it easier to find a later number that 
            # is increasing).                                                          
            # Thus, we look for the smallest element in                                
            # smallest_end_to_subsequence_of_length that is at least as big as elem       
            # and replace it with elem.                                                
            # This preserves correctness because if there is a subsequence of length n 
            # that ends with a number smaller than elem, we could add elem on to the   
            # end of that subsequence to get a subsequence of length n+1.              
            location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
            smallest_end_to_subsequence_of_length[location_to_replace] = elem
            # If we're replacing the first element, we don't need to update its parent 
            # because a subsequence of length 1 has no parent.  Otherwise, its parent  
            # is the subsequence one shorter, which we just added onto.                
            if location_to_replace != 0:
                parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1])

    # Generate the longest increasing subsequence by backtracking through parent.  
    curr_parent = smallest_end_to_subsequence_of_length[-1]
    longest_increasing_subsequence = []

    while curr_parent is not None:
        longest_increasing_subsequence.append(sequence[curr_parent])
        curr_parent = parent[curr_parent]

    longest_increasing_subsequence.reverse()

    return longest_increasing_subsequence         
53
Sam King

In Bezug auf die DP-Lösung war es überraschend, dass niemand die Tatsache erwähnt hat, dass LIS auf LCS reduziert werden kann. Alles, was Sie tun müssen, ist die Kopie der Originalsequenz zu sortieren, alle Duplikate zu entfernen und LCS von ihnen auszuführen. Im Pseudocode heißt es:

def LIS(S):
    T = sort(S)
    T = removeDuplicates(T)
    return LCS(S, T)

Und die vollständige Implementierung in Go geschrieben. Sie müssen die gesamte n ^ 2 DP-Matrix nicht warten, wenn Sie die Lösung nicht rekonstruieren müssen.

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]
}
19
Salvador Dali

Die folgende C++ - Implementierung enthält auch etwas Code, der die tatsächliche am längsten zunehmende Untersequenz mithilfe eines Arrays mit dem Namen prev erstellt.

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();

    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.Push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.Push_back(stk.top());
        stk.pop();
    }

    return results;
}

Implementierung ohne Stack kehrt den Vektor um 

#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
  auto sz = v.size();
  if(!sz)
    return v;
  std::vector<int> memo(sz, 0);
  std::vector<int> prev(sz, -1);
  memo[0] = 1;
  int best_end = 0;
  int max_length = std::numeric_limits<int>::min();
  for (auto i = 1; i < sz; ++i) {
    for ( auto j = 0; j < i ; ++j) {
      if (s[j] < s[i] && memo[i] < memo[j] + 1) {
        memo[i] = memo[j] + 1;
        prev[i] = j;
      }
    }
    if(memo[i] > max_length) {
      best_end = i;
      max_length = memo[i];
    }
  }

  // create results
  std::vector<int> results;
  results.reserve(v.size());
  auto current = best_end;
  while (current != -1) {
    results.Push_back(s[current]);
    current = prev[current];
  }
  std::reverse(results.begin(), results.end());
  return results;
}
9
bjackfly

Hier sind drei Schritte zur Bewertung des Problems aus Sicht der dynamischen Programmierung:

  1. Wiederholungsdefinition: maxLength (i) == 1 + maxLength (j) wobei 0 <j <i und Array [i]> Array [j]
  2. Wiederholungsparametergrenze: Es können 0 bis i - 1 Subsequenzen als Parameter übergeben werden
  3. Auswertungsreihenfolge: Da die Teilsequenz ansteigt, muss sie von 0 bis n bewertet werden

Wenn wir die Sequenz {0, 8, 2, 3, 7, 9} am Index nehmen:

  • [0] Wir erhalten die Untersequenz {0} als Basisfall
  • [1] wir haben 1 neue Untersequenz {0, 8}
  • [2] beim Versuch, zwei neue Sequenzen {0, 8, 2} und {0, 2} auszuwerten, indem Element zu Index 2 zu vorhandenen Subsequenzen hinzugefügt wird - nur eine ist gültig, also nur die dritte mögliche Sequenz {0, 2} zur Parameterliste ...

Hier ist der funktionierende C++ 11-Code:

#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;
}
3
Iuri Covalisin

Hier ist eine Scala-Implementierung des O (n ^ 2) -Algorithmus:

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)))
  }
}
1
lcn

Hier ist eine weitere O (n ^ 2) Java-Implementierung. Keine Rekursion/Memoization zur Erzeugung der tatsächlichen Untersequenz. Nur ein String-Array, das das tatsächliche LIS in jeder Phase speichert, und ein Array, in dem die Länge des LIS für jedes Element gespeichert wird. Ziemlich einfach. Guck mal:

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

Code in Aktion: http://ideone.com/sBiOQx

1
bholagabbar

O (n ^ 2) Java-Implementierung:

void LIS(int arr[]){
        int maxCount[]=new int[arr.length];
        int link[]=new int[arr.length];
        int maxI=0;
        link[0]=0;
        maxCount[0]=0;

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if(arr[j]<arr[i] && ((maxCount[j]+1)>maxCount[i])){
                    maxCount[i]=maxCount[j]+1;
                    link[i]=j;
                    if(maxCount[i]>maxCount[maxI]){
                        maxI=i;
                    }
                }
            }
        }


        for (int i = 0; i < link.length; i++) {
            System.out.println(arr[i]+"   "+link[i]);
        }
        print(arr,maxI,link);

    }

    void print(int arr[],int index,int link[]){
        if(link[index]==index){
            System.out.println(arr[index]+" ");
            return;
        }else{
            print(arr, link[index], link);
            System.out.println(arr[index]+" ");
        }
    }
0
Mostafizar

Dies kann durch dynamische Programmierung in O (n ^ 2) gelöst werden. Python-Code für das gleiche wäre: -

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)

Für die Eingabe: 5 19 5 81 50 28 29 1 83 23

ausgabe wäre: [1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5

Der listeindex der Ausgabeliste ist der listeindex der Eingabeliste. Der Wert an einem bestimmten list_index in der Ausgabeliste gibt die am längsten wachsende Teilsequenzlänge für diesen list_index an.

0
Barun Sharma

Dies ist eine Java-Implementierung in O (n ^ 2). Ich habe einfach nicht die binäre Suche verwendet, um das kleinste Element in S zu finden, das> = als X ist. Ich habe nur eine for-Schleife verwendet. Die Verwendung der binären Suche würde die Komplexität bei O (n logn) erhöhen.

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

}
0
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)

es gibt zwar einen Weg, auf dem Sie dies in der Zeit O(nlogn) lösen können (dies löst sich in der Zeit O (n ^ 2) auf), aber dennoch gibt es den dynamischen Programmieransatz, der ebenfalls gut ist. 

0
ravi tanwar

Hier ist meine Leetcode-Lösung mit der binären Suche: ->

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)
0
Abhinav Vajpeyi

Einfachste LIS-Lösung in C++ mit O(nlog(n)) Zeitkomplexität

#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;
}

AUSGABE:
4

0
Ashish kumar

checkout den Code in Java für die am längsten wachsende Teilsequenz mit den Array-Elementen

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();
    }
}
0
jayant singh

Dies kann durch dynamische Programmierung in O (n ^ 2) gelöst werden.

Verarbeiten Sie die Eingabeelemente in Reihenfolge und pflegen Sie eine Liste von Tupeln für jedes Element. Jeder Tupel (A, B) für das Element i wird bedeuten: A = Länge der am längsten zunehmenden Teilsequenz, die bei i endet, und B = Index des Vorgängers der Liste [i] in der am längsten zunehmenden Teilsequenz, die an der Liste [i ].

Beginnend bei Element 1 ist die Liste von Tuple für Element 1 [(1,0)] Für Element i, scannen Sie die Liste 0..i und suchen Sie die Elementliste [k] nach dieser Liste [k] <Liste [i], der Wert von A für Element i, Ai ist Ak + 1 und Bi ist k. Wenn mehrere solcher Elemente vorhanden sind, fügen Sie sie der Liste der Tupel für Element i hinzu.

Suchen Sie am Ende alle Elemente mit dem maximalen Wert von A (Länge des LIS, die bei element endet) und gehen Sie zurück, indem Sie die Tupel verwenden, um die Liste abzurufen.

Ich habe den Code für denselben unter http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799 geteilt

0
Somil Bhandari

hier ist die Implementierung von 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);
    }    
}
0
fatih tekin