Tipărirea celei mai lungi secvențe bitonice
Problema celei mai lungi subsecvențe bitonice este de a găsi cea mai lungă subsecvență a unei secvențe date astfel încât să crească mai întâi și apoi să descrească. O secvență sortată în ordine crescătoare este considerată Bitonică cu partea descrescătoare ca fiind goală. În mod similar, secvența de ordine descrescătoare este considerată Bitonică, cu partea crescătoare ca fiind goală. Exemple:
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]
În anterior post pe care am discutat despre problema celei mai lungi subsecvențe bitonice. Cu toate acestea, postarea a acoperit doar codul legat de găsirea sumei maxime a subsecvenței crescătoare, dar nu și a construcției subsecvenței. În această postare vom discuta despre cum să construim cea mai lungă subsecvență bitonic în sine. Fie arr[0..n-1] tabloul de intrare. Definim vectorul LIS astfel încât LIS[i] este el însuși un vector care stochează cea mai lungă subsecvență crescătoare a arr[0..i] care se termină cu arr[i]. Prin urmare, pentru un index i LIS[i] poate fi scris recursiv ca -
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 De asemenea, definim un vector LDS astfel încât LDS[i] este el însuși un vector care stochează cea mai lungă subsecvență descrescătoare a arr[i..n] care începe cu arr[i]. Prin urmare, pentru un index i LDS[i] poate fi scris recursiv ca -
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 De exemplu, pentru matrice [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
Prin urmare, cea mai lungă subsecvență bitonică poate fi
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]
Mai jos este implementarea ideii de mai sus -
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 );
Ieșire:
1 11 10 5 2 1
Complexitatea timpului soluția de programare dinamică de mai sus este O(n 2 ). Spațiu auxiliar folosit de program este O(n 2 ).
