Skriver ut längsta bitoniska efterföljd
Problemet med längsta bitoniska delsekvens är att hitta den längsta delsekvensen av en given sekvens så att den först ökar och sedan minskar. En sekvens sorterad i ökande ordning anses Bitonic med den minskande delen som tom. Liknande fallande ordningsföljd anses vara Bitonic med den ökande delen som tom. Exempel:
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]
I tidigare inlägg vi har diskuterat om Longest Bitonic Subsequence-problem. Men inlägget omfattade endast kod som gällde att hitta den maximala summan av ökande efterföljd men inte till konstruktionen av efterföljd. I det här inlägget kommer vi att diskutera hur man konstruerar Longest Bitonic Subsequence själv. Låt arr[0..n-1] vara inmatningsmatrisen. Vi definierar vektor LIS så att LIS[i] i sig själv är en vektor som lagrar längsta ökande delsekvens av arr[0..i] som slutar med arr[i]. Därför kan för ett index i LIS[i] skrivas rekursivt som -
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 Vi definierar också en vektor LDS så att LDS[i] i sig själv är en vektor som lagrar längsta minskande undersekvens av arr[i..n] som börjar med arr[i]. Därför för ett index kan i LDS[i] skrivas rekursivt som -
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 Till exempel 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
Därför kan den längsta bitoniska subsekvensen vara
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]
Nedan är implementeringen av ovanstående idé -
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 );
Produktion:
1 11 10 5 2 1
Tidskomplexitet av ovanstående dynamisk programmeringslösning är O(n 2 ). Hjälputrymme som används av programmet är O(n 2 ).
