En Uzun Bitonik Diziyi Yazdırma
En Uzun Bitonik Alt Dizi problemi, belirli bir dizinin önce artan, sonra azalan en uzun alt dizisini bulmaktır. Artan düzende sıralanan bir dizi, azalan kısmı boş olan Bitonik olarak kabul edilir. Benzer şekilde azalan sıra dizisi, artan kısmı boş olacak şekilde Bitonik olarak kabul edilir. Örnekler:
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]
İçinde öncesi Bu yazımızda En Uzun Bitonik Alt Dizi problemini tartışmıştık. Bununla birlikte, yazı yalnızca artan alt dizinin maksimum toplamını bulmayla ilgili kodu kapsıyordu, ancak alt diziyi oluşturmayla ilgili değildi. Bu yazıda En Uzun Bitonik Alt Dizinin kendisini nasıl oluşturacağımızı tartışacağız. arr[0..n-1] giriş dizisi olsun. LIS vektörünü, LIS[i]'nin kendisi arr[0..i]'nin arr[i] ile biten En Uzun Artan Alt Dizisini saklayan bir vektör olacak şekilde tanımlarız. Bu nedenle bir indeks için i LIS[i] yinelemeli olarak şu şekilde yazılabilir:
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 Ayrıca LDS[i]'nin kendisi arr[i] ile başlayan arr[i..n]'nin En Uzun Azalan Sırasını saklayan bir vektör olacak şekilde bir LDS vektörü tanımlarız. Bu nedenle, bir i LDS[i] indeksi için yinelemeli olarak şu şekilde yazılabilir:
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 Örneğin [1 11 2 10 4 5 2 1] dizisi için
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
Bu nedenle En Uzun Bitonik Alt Dizi şu şekilde olabilir:
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]
Aşağıda yukarıdaki fikrin uygulanması yer almaktadır -
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 );
Çıkış:
1 11 10 5 2 1
Zaman karmaşıklığı Yukarıdaki Dinamik Programlama çözümünün O(n) 2 ). Yardımcı alan program tarafından kullanılan O(n 2 ).
