Drucken der längsten bitonischen Folge
Das Problem der längsten bitonischen Teilfolge besteht darin, die längste Teilfolge einer gegebenen Folge so zu finden, dass sie zuerst zu- und dann abnimmt. Eine in aufsteigender Reihenfolge sortierte Sequenz wird als bitonisch betrachtet, wobei der absteigende Teil leer ist. Eine ähnlich absteigende Reihenfolge wird als bitonisch betrachtet, wobei der aufsteigende Teil leer ist. Beispiele:
Input: [1 11 2 10 4 5 2 1] Output: [1 2 10 4 2 1] OR [1 11 10 5 2 1] OR [1 2 4 5 2 1] Input: [12 11 40 5 3 1] Output: [12 11 5 3 1] OR [12 40 5 3 1] Input: [80 60 30 40 20 10] Output: [80 60 30 20 10] OR [80 60 40 20 10]
In vorherige Beitrag, den wir über das Problem der längsten bitonischen Teilsequenz besprochen haben. Der Beitrag befasste sich jedoch nur mit Code, der sich auf die Ermittlung der Maximalsumme ansteigender Teilsequenzen bezieht, nicht jedoch auf die Konstruktion von Teilsequenzen. In diesem Beitrag besprechen wir, wie man die längste bitonische Teilsequenz selbst erstellt. Sei arr[0..n-1] das Eingabearray. Wir definieren den Vektor LIS so, dass LIS[i] selbst ein Vektor ist, der die am längsten ansteigende Teilfolge von arr[0..i] speichert, die mit arr[i] endet. Daher kann LIS[i] für einen Index i rekursiv geschrieben werden als -
LIS[0] = {arr[O]} LIS[i] = {Max(LIS[j])} + arr[i] where j < i and arr[j] < arr[i] = arr[i] if there is no such j Wir definieren auch einen Vektor LDS, sodass LDS[i] selbst ein Vektor ist, der die am längsten abnehmende Teilfolge von arr[i..n] speichert, die mit arr[i] beginnt. Daher kann LDS[i] für einen Index i rekursiv geschrieben werden als -
LDS[n] = {arr[n]} LDS[i] = arr[i] + {Max(LDS[j])} where j > i and arr[j] < arr[i] = arr[i] if there is no such j Zum Beispiel für Array [1 11 2 10 4 5 2 1]
LIS[0]: 1 LIS[1]: 1 11 LIS[2]: 1 2 LIS[3]: 1 2 10 LIS[4]: 1 2 4 LIS[5]: 1 2 4 5 LIS[6]: 1 2 LIS[7]: 1
LDS[0]: 1 LDS[1]: 11 10 5 2 1 LDS[2]: 2 1 LDS[3]: 10 5 2 1 LDS[4]: 4 2 1 LDS[5]: 5 2 1 LDS[6]: 2 1 LDS[7]: 1
Daher kann die längste bitonische Folge sein
LIS[1] + LDS[1] = [1 11 10 5 2 1] OR LIS[3] + LDS[3] = [1 2 10 5 2 1] OR LIS[5] + LDS[5] = [1 2 4 5 2 1]
Nachfolgend finden Sie die Umsetzung der obigen Idee:
C++ /* Dynamic Programming solution to print Longest Bitonic Subsequence */ #include using namespace std ; // Utility function to print Longest Bitonic // Subsequence void print ( vector < int >& arr int size ) { for ( int i = 0 ; i < size ; i ++ ) cout < < arr [ i ] < < ' ' ; } // Function to construct and print Longest // Bitonic Subsequence void printLBS ( int arr [] int n ) { // LIS[i] stores the length of the longest // increasing subsequence ending with arr[i] vector < vector < int >> LIS ( n ); // initialize LIS[0] to arr[0] LIS [ 0 ]. push_back ( arr [ 0 ]); // Compute LIS values from left to right for ( int i = 1 ; i < n ; i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { if (( arr [ j ] < arr [ i ]) && ( LIS [ j ]. size () > LIS [ i ]. size ())) LIS [ i ] = LIS [ j ]; } LIS [ i ]. push_back ( arr [ i ]); } /* LIS[i] now stores Maximum Increasing Subsequence of arr[0..i] that ends with arr[i] */ // LDS[i] stores the length of the longest // decreasing subsequence starting with arr[i] vector < vector < int >> LDS ( n ); // initialize LDS[n-1] to arr[n-1] LDS [ n - 1 ]. push_back ( arr [ n - 1 ]); // Compute LDS values from right to left for ( int i = n - 2 ; i >= 0 ; i -- ) { // for every j greater than i for ( int j = n - 1 ; j > i ; j -- ) { if (( arr [ j ] < arr [ i ]) && ( LDS [ j ]. size () > LDS [ i ]. size ())) LDS [ i ] = LDS [ j ]; } LDS [ i ]. push_back ( arr [ i ]); } // reverse as vector as we're inserting at end for ( int i = 0 ; i < n ; i ++ ) reverse ( LDS [ i ]. begin () LDS [ i ]. end ()); /* LDS[i] now stores Maximum Decreasing Subsequence of arr[i..n] that starts with arr[i] */ int max = 0 ; int maxIndex = -1 ; for ( int i = 0 ; i < n ; i ++ ) { // Find maximum value of size of LIS[i] + size // of LDS[i] - 1 if ( LIS [ i ]. size () + LDS [ i ]. size () - 1 > max ) { max = LIS [ i ]. size () + LDS [ i ]. size () - 1 ; maxIndex = i ; } } // print all but last element of LIS[maxIndex] vector print ( LIS [ maxIndex ] LIS [ maxIndex ]. size () - 1 ); // print all elements of LDS[maxIndex] vector print ( LDS [ maxIndex ] LDS [ maxIndex ]. size ()); } // Driver program int main () { int arr [] = { 1 11 2 10 4 5 2 1 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); printLBS ( arr n ); return 0 ; }
Java /* Dynamic Programming solution to print Longest Bitonic Subsequence */ import java.util.* ; class GFG { // Utility function to print Longest Bitonic // Subsequence static void print ( Vector < Integer > arr int size ) { for ( int i = 0 ; i < size ; i ++ ) System . out . print ( arr . elementAt ( i ) + ' ' ); } // Function to construct and print Longest // Bitonic Subsequence static void printLBS ( int [] arr int n ) { // LIS[i] stores the length of the longest // increasing subsequence ending with arr[i] @SuppressWarnings ( 'unchecked' ) Vector < Integer >[] LIS = new Vector [ n ] ; for ( int i = 0 ; i < n ; i ++ ) LIS [ i ] = new Vector <> (); // initialize LIS[0] to arr[0] LIS [ 0 ] . add ( arr [ 0 ] ); // Compute LIS values from left to right for ( int i = 1 ; i < n ; i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { if (( arr [ i ] > arr [ j ] ) && LIS [ j ] . size () > LIS [ i ] . size ()) { for ( int k : LIS [ j ] ) if ( ! LIS [ i ] . contains ( k )) LIS [ i ] . add ( k ); } } LIS [ i ] . add ( arr [ i ] ); } /* * LIS[i] now stores Maximum Increasing Subsequence * of arr[0..i] that ends with arr[i] */ // LDS[i] stores the length of the longest // decreasing subsequence starting with arr[i] @SuppressWarnings ( 'unchecked' ) Vector < Integer >[] LDS = new Vector [ n ] ; for ( int i = 0 ; i < n ; i ++ ) LDS [ i ] = new Vector <> (); // initialize LDS[n-1] to arr[n-1] LDS [ n - 1 ] . add ( arr [ n - 1 ] ); // Compute LDS values from right to left for ( int i = n - 2 ; i >= 0 ; i -- ) { // for every j greater than i for ( int j = n - 1 ; j > i ; j -- ) { if ( arr [ j ] < arr [ i ] && LDS [ j ] . size () > LDS [ i ] . size ()) for ( int k : LDS [ j ] ) if ( ! LDS [ i ] . contains ( k )) LDS [ i ] . add ( k ); } LDS [ i ] . add ( arr [ i ] ); } // reverse as vector as we're inserting at end for ( int i = 0 ; i < n ; i ++ ) Collections . reverse ( LDS [ i ] ); /* * LDS[i] now stores Maximum Decreasing Subsequence * of arr[i..n] that starts with arr[i] */ int max = 0 ; int maxIndex = - 1 ; for ( int i = 0 ; i < n ; i ++ ) { // Find maximum value of size of // LIS[i] + size of LDS[i] - 1 if ( LIS [ i ] . size () + LDS [ i ] . size () - 1 > max ) { max = LIS [ i ] . size () + LDS [ i ] . size () - 1 ; maxIndex = i ; } } // print all but last element of LIS[maxIndex] vector print ( LIS [ maxIndex ] LIS [ maxIndex ] . size () - 1 ); // print all elements of LDS[maxIndex] vector print ( LDS [ maxIndex ] LDS [ maxIndex ] . size ()); } // Driver Code public static void main ( String [] args ) { int [] arr = { 1 11 2 10 4 5 2 1 }; int n = arr . length ; printLBS ( arr n ); } } // This code is contributed by // sanjeev2552
Python3 # Dynamic Programming solution to print Longest # Bitonic Subsequence def _print ( arr : list size : int ): for i in range ( size ): print ( arr [ i ] end = ' ' ) # Function to construct and print Longest # Bitonic Subsequence def printLBS ( arr : list n : int ): # LIS[i] stores the length of the longest # increasing subsequence ending with arr[i] LIS = [ 0 ] * n for i in range ( n ): LIS [ i ] = [] # initialize LIS[0] to arr[0] LIS [ 0 ] . append ( arr [ 0 ]) # Compute LIS values from left to right for i in range ( 1 n ): # for every j less than i for j in range ( i ): if (( arr [ j ] < arr [ i ]) and ( len ( LIS [ j ]) > len ( LIS [ i ]))): LIS [ i ] = LIS [ j ] . copy () LIS [ i ] . append ( arr [ i ]) # LIS[i] now stores Maximum Increasing # Subsequence of arr[0..i] that ends with # arr[i] # LDS[i] stores the length of the longest # decreasing subsequence starting with arr[i] LDS = [ 0 ] * n for i in range ( n ): LDS [ i ] = [] # initialize LDS[n-1] to arr[n-1] LDS [ n - 1 ] . append ( arr [ n - 1 ]) # Compute LDS values from right to left for i in range ( n - 2 - 1 - 1 ): # for every j greater than i for j in range ( n - 1 i - 1 ): if (( arr [ j ] < arr [ i ]) and ( len ( LDS [ j ]) > len ( LDS [ i ]))): LDS [ i ] = LDS [ j ] . copy () LDS [ i ] . append ( arr [ i ]) # reverse as vector as we're inserting at end for i in range ( n ): LDS [ i ] = list ( reversed ( LDS [ i ])) # LDS[i] now stores Maximum Decreasing Subsequence # of arr[i..n] that starts with arr[i] max = 0 maxIndex = - 1 for i in range ( n ): # Find maximum value of size of LIS[i] + size # of LDS[i] - 1 if ( len ( LIS [ i ]) + len ( LDS [ i ]) - 1 > max ): max = len ( LIS [ i ]) + len ( LDS [ i ]) - 1 maxIndex = i # print all but last element of LIS[maxIndex] vector _print ( LIS [ maxIndex ] len ( LIS [ maxIndex ]) - 1 ) # print all elements of LDS[maxIndex] vector _print ( LDS [ maxIndex ] len ( LDS [ maxIndex ])) # Driver Code if __name__ == '__main__' : arr = [ 1 11 2 10 4 5 2 1 ] n = len ( arr ) printLBS ( arr n ) # This code is contributed by # sanjeev2552
C# /* Dynamic Programming solution to print longest Bitonic Subsequence */ using System ; using System.Linq ; using System.Collections.Generic ; class GFG { // Utility function to print longest Bitonic // Subsequence static void print ( List < int > arr int size ) { for ( int i = 0 ; i < size ; i ++ ) Console . Write ( arr [ i ] + ' ' ); } // Function to construct and print longest // Bitonic Subsequence static void printLBS ( int [] arr int n ) { // LIS[i] stores the length of the longest // increasing subsequence ending with arr[i] List < int > [] LIS = new List < int > [ n ]; for ( int i = 0 ; i < n ; i ++ ) LIS [ i ] = new List < int > (); // initialize LIS[0] to arr[0] LIS [ 0 ]. Add ( arr [ 0 ]); // Compute LIS values from left to right for ( int i = 1 ; i < n ; i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { if (( arr [ i ] > arr [ j ]) && LIS [ j ]. Count > LIS [ i ]. Count ) { foreach ( int k in LIS [ j ]) if ( ! LIS [ i ]. Contains ( k )) LIS [ i ]. Add ( k ); } } LIS [ i ]. Add ( arr [ i ]); } /* * LIS[i] now stores Maximum Increasing Subsequence * of arr[0..i] that ends with arr[i] */ // LDS[i] stores the length of the longest // decreasing subsequence starting with arr[i] List < int > [] LDS = new List < int > [ n ]; for ( int i = 0 ; i < n ; i ++ ) LDS [ i ] = new List < int > (); // initialize LDS[n-1] to arr[n-1] LDS [ n - 1 ]. Add ( arr [ n - 1 ]); // Compute LDS values from right to left for ( int i = n - 2 ; i >= 0 ; i -- ) { // for every j greater than i for ( int j = n - 1 ; j > i ; j -- ) { if ( arr [ j ] < arr [ i ] && LDS [ j ]. Count > LDS [ i ]. Count ) foreach ( int k in LDS [ j ]) if ( ! LDS [ i ]. Contains ( k )) LDS [ i ]. Add ( k ); } LDS [ i ]. Add ( arr [ i ]); } // reverse as vector as we're inserting at end for ( int i = 0 ; i < n ; i ++ ) LDS [ i ]. Reverse (); /* * LDS[i] now stores Maximum Decreasing Subsequence * of arr[i..n] that starts with arr[i] */ int max = 0 ; int maxIndex = - 1 ; for ( int i = 0 ; i < n ; i ++ ) { // Find maximum value of size of // LIS[i] + size of LDS[i] - 1 if ( LIS [ i ]. Count + LDS [ i ]. Count - 1 > max ) { max = LIS [ i ]. Count + LDS [ i ]. Count - 1 ; maxIndex = i ; } } // print all but last element of LIS[maxIndex] vector print ( LIS [ maxIndex ] LIS [ maxIndex ]. Count - 1 ); // print all elements of LDS[maxIndex] vector print ( LDS [ maxIndex ] LDS [ maxIndex ]. Count ); } // Driver Code public static void Main ( String [] args ) { int [] arr = { 1 11 2 10 4 5 2 1 }; int n = arr . Length ; printLBS ( arr n ); } } // This code is contributed by PrinciRaj1992
JavaScript // Function to print the longest bitonic subsequence function _print ( arr size ) { for ( let i = 0 ; i < size ; i ++ ) { process . stdout . write ( arr [ i ] + ' ' ); } } // Function to construct and print the longest bitonic subsequence function printLBS ( arr n ) { // LIS[i] stores the length of the longest increasing subsequence ending with arr[i] let LIS = new Array ( n ); for ( let i = 0 ; i < n ; i ++ ) { LIS [ i ] = []; } // initialize LIS[0] to arr[0] LIS [ 0 ]. push ( arr [ 0 ]); // Compute LIS values from left to right for ( let i = 1 ; i < n ; i ++ ) { // for every j less than i for ( let j = 0 ; j < i ; j ++ ) { if ( arr [ j ] < arr [ i ] && LIS [ j ]. length > LIS [ i ]. length ) { LIS [ i ] = LIS [ j ]. slice (); } } LIS [ i ]. push ( arr [ i ]); } // LIS[i] now stores the Maximum Increasing Subsequence of arr[0..i] that ends with arr[i] // LDS[i] stores the length of the longest decreasing subsequence starting with arr[i] let LDS = new Array ( n ); for ( let i = 0 ; i < n ; i ++ ) { LDS [ i ] = []; } // initialize LDS[n-1] to arr[n-1] LDS [ n - 1 ]. push ( arr [ n - 1 ]); // Compute LDS values from right to left for ( let i = n - 2 ; i >= 0 ; i -- ) { // for every j greater than i for ( let j = n - 1 ; j > i ; j -- ) { if ( arr [ j ] < arr [ i ] && LDS [ j ]. length > LDS [ i ]. length ) { LDS [ i ] = LDS [ j ]. slice (); } } LDS [ i ]. push ( arr [ i ]); } // reverse the LDS vector as we're inserting at the end for ( let i = 0 ; i < n ; i ++ ) { LDS [ i ]. reverse (); } // LDS[i] now stores the Maximum Decreasing Subsequence of arr[i..n] that starts with arr[i] let max = 0 ; let maxIndex = - 1 ; for ( let i = 0 ; i < n ; i ++ ) { // Find maximum value of size of LIS[i] + size of LDS[i] - 1 if ( LIS [ i ]. length + LDS [ i ]. length - 1 > max ) { max = LIS [ i ]. length + LDS [ i ]. length - 1 ; maxIndex = i ; } } // print all but // print all but last element of LIS[maxIndex] array _print ( LIS [ maxIndex ]. slice ( 0 - 1 ) LIS [ maxIndex ]. length - 1 ); // print all elements of LDS[maxIndex] array _print ( LDS [ maxIndex ] LDS [ maxIndex ]. length ); } // Driver program const arr = [ 1 11 2 10 4 5 2 1 ]; const n = arr . length ; printLBS ( arr n );
Ausgabe:
1 11 10 5 2 1
Zeitkomplexität Die obige dynamische Programmierlösung ist O(n 2 ). Hilfsraum vom Programm verwendet wird, ist O(n 2 ).
