Garākās bitoniskās secības drukāšana
Garākās bitoniskās apakšsecības problēma ir atrast noteiktās sekvences garāko apakšsekvenci, lai tā vispirms palielinātos un pēc tam samazinātos. Secība, kas sakārtota augošā secībā, tiek uzskatīta par bitonisku un dilstošā daļa ir tukša. Līdzīgi dilstošā secība tiek uzskatīta par bitonisku ar pieaugošo daļu kā tukšu. Piemēri:
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 iepriekšējā ziņa, ko esam apsprieduši par garākās bitoniskās sekvences problēmu. Tomēr ziņojumā bija ietverts tikai kods, kas saistīts ar pieaugošās apakšsecības maksimālās summas atrašanu, bet ne uz apakšsecības veidošanu. Šajā rakstā mēs apspriedīsim, kā izveidot pašu garāko bitonisko apakšsekvenci. Ļaujiet arr[0..n-1] būt ievades masīvam. Mēs definējam vektoru LIS tā, lai LIS[i] pats par sevi ir vektors, kas saglabā arr[0..i] garāko pieaugošo apakšsekvenci, kas beidzas ar arr[i]. Tāpēc indeksam i LIS[i] var rekursīvi uzrakstīt kā -
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 Mēs arī definējam vektoru LDS tā, ka LDS[i] pats par sevi ir vektors, kas saglabā arr[i..n] garāko dilstošo apakšsekvenci, kas sākas ar arr[i]. Tāpēc indeksam i LDS[i] var rekursīvi uzrakstīt kā -
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 Piemēram, masīvam [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
Tāpēc var būt garākā bitoniskā apakšsekvencija
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]
Zemāk ir iepriekš minētās idejas īstenošana -
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 );
Izvade:
1 11 10 5 2 1
Laika sarežģītība Dinamiskās programmēšanas risinājums ir O(n 2 ). Palīgtelpa Programma izmanto O (n 2 ).
