Tisk maximálního součtu rostoucí následné sekvence
Zkuste to na GfG Practice 
Výstup
Problémem podsekvence maximálního součtu je najít podsekvenci maximálního součtu dané sekvence tak, že všechny prvky podsekvence jsou seřazeny v rostoucím pořadí.
Příklady:
Input: [1 101 2 3 100 4 5]
Output: [1 2 3 100]
Input: [3 4 5 10]
Output: [3 4 5 10]
Input: [10 5 4 3]
Output: [10]
Input: [3 2 6 4 5 1]
Output: [3 4 5]V předchozím příspěvku jsme diskutovali o problému se zvyšující se podsekvencí maximálního součtu. Příspěvek se však týkal pouze kódu souvisejícího s nalezením maximálního součtu rostoucí subsekvence, ale nikoli konstrukce subsekvence. V tomto příspěvku budeme diskutovat o tom, jak vytvořit samotnou subsekvenci zvyšující maximální součet.
Nechť arr[0..n-1] je vstupní pole. Vektor L definujeme tak, že L[i] je samo o sobě vektor, který ukládá podsekvenci maximálního součtu rostoucího arr[0..i], která končí arr[i]. Proto pro index i L[i] lze rekurzivně zapsat jako
L[0] = {arr[0]}
L[i] = {MaxSum(L[j])} + arr[i] where j < i and arr[j] < arr[i]
= arr[i] if there is no j such that arr[j] < arr[i]
Například pro pole [3 2 6 4 5 1]L[0]: 3
L[1]: 2
L[2]: 3 6
L[3]: 3 4
L[4]: 3 4 5
L[5]: 1C++
Níže je uvedena implementace výše uvedené myšlenky –Java/* Dynamic Programming solution to construct Maximum Sum Increasing Subsequence */ #include#include using namespace std ; // Utility function to calculate sum of all // vector elements int findSum ( vector < int > arr ) { int sum = 0 ; for ( int i : arr ) sum += i ; return sum ; } // Function to construct Maximum Sum Increasing // Subsequence void printMaxSumIS ( int arr [] int n ) { // L[i] - The Maximum Sum Increasing // Subsequence that ends with arr[i] vector < vector < int > > L ( n ); // L[0] is equal to arr[0] L [ 0 ]. push_back ( arr [ 0 ]); // start from index 1 for ( int i = 1 ; i < n ; i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { /* L[i] = {MaxSum(L[j])} + arr[i] where j < i and arr[j] < arr[i] */ if (( arr [ i ] > arr [ j ]) && ( findSum ( L [ i ]) < findSum ( L [ j ]))) L [ i ] = L [ j ]; } // L[i] ends with arr[i] L [ i ]. push_back ( arr [ i ]); // L[i] now stores Maximum Sum Increasing // Subsequence of arr[0..i] that ends with // arr[i] } vector < int > res = L [ 0 ]; // find max for ( vector < int > x : L ) if ( findSum ( x ) > findSum ( res )) res = x ; // max will contain result for ( int i : res ) cout < < i < < ' ' ; cout < < endl ; } // Driver Code int main () { int arr [] = { 3 2 6 4 5 1 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); // construct and print Max Sum IS of arr printMaxSumIS ( arr n ); return 0 ; } Python/* Dynamic Programming solution to construct Maximum Sum Increasing Subsequence */ import java.util.* ; class GFG { // Utility function to calculate sum of all // vector elements static int findSum ( Vector < Integer > arr ) { int sum = 0 ; for ( int i : arr ) sum += i ; return sum ; } // Function to construct Maximum Sum Increasing // Subsequence static void printMaxSumIs ( int [] arr int n ) { // L[i] - The Maximum Sum Increasing // Subsequence that ends with arr[i] @SuppressWarnings ( 'unchecked' ) Vector < Integer >[] L = new Vector [ n ] ; for ( int i = 0 ; i < n ; i ++ ) L [ i ] = new Vector <> (); // L[0] is equal to arr[0] L [ 0 ] . add ( arr [ 0 ] ); // start from index 1 for ( int i = 1 ; i < n ; i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { /* * L[i] = {MaxSum(L[j])} + arr[i] where j < i and arr[j] < arr[i] */ if (( arr [ i ] > arr [ j ] ) && ( findSum ( L [ i ] ) < findSum ( L [ j ] ))) { for ( int k : L [ j ] ) if ( ! L [ i ] . contains ( k )) L [ i ] . add ( k ); } } // L[i] ends with arr[i] L [ i ] . add ( arr [ i ] ); // L[i] now stores Maximum Sum Increasing // Subsequence of arr[0..i] that ends with // arr[i] } Vector < Integer > res = new Vector <> ( L [ 0 ] ); // res = L[0]; // find max for ( Vector < Integer > x : L ) if ( findSum ( x ) > findSum ( res )) res = x ; // max will contain result for ( int i : res ) System . out . print ( i + ' ' ); System . out . println (); } // Driver Code public static void main ( String [] args ) { int [] arr = { 3 2 6 4 5 1 }; int n = arr . length ; // construct and print Max Sum IS of arr printMaxSumIs ( arr n ); } } // This code is contributed by // sanjeev2552C## Dynamic Programming solution to construct # Maximum Sum Increasing Subsequence */ # Utility function to calculate sum of all # vector elements def findSum ( arr ): summ = 0 for i in arr : summ += i return summ # Function to construct Maximum Sum Increasing # Subsequence def printMaxSumIS ( arr n ): # L[i] - The Maximum Sum Increasing # Subsequence that ends with arr[i] L = [[] for i in range ( n )] # L[0] is equal to arr[0] L [ 0 ] . append ( arr [ 0 ]) # start from index 1 for i in range ( 1 n ): # for every j less than i for j in range ( i ): # L[i] = {MaxSum(L[j])} + arr[i] # where j < i and arr[j] < arr[i] if (( arr [ i ] > arr [ j ]) and ( findSum ( L [ i ]) < findSum ( L [ j ]))): for e in L [ j ]: if e not in L [ i ]: L [ i ] . append ( e ) # L[i] ends with arr[i] L [ i ] . append ( arr [ i ]) # L[i] now stores Maximum Sum Increasing # Subsequence of arr[0..i] that ends with # arr[i] res = L [ 0 ] # find max for x in L : if ( findSum ( x ) > findSum ( res )): res = x # max will contain result for i in res : print ( i end = ' ' ) # Driver Code arr = [ 3 2 6 4 5 1 ] n = len ( arr ) # construct and prMax Sum IS of arr printMaxSumIS ( arr n ) # This code is contributed by Mohit KumarJavaScript/* Dynamic Programming solution to construct Maximum Sum Increasing Subsequence */ using System ; using System.Collections.Generic ; class GFG { // Utility function to calculate sum of all // vector elements static int findSum ( List < int > arr ) { int sum = 0 ; foreach ( int i in arr ) sum += i ; return sum ; } // Function to construct Maximum Sum Increasing // Subsequence static void printMaxSumIs ( int [] arr int n ) { // L[i] - The Maximum Sum Increasing // Subsequence that ends with arr[i] List < int > [] L = new List < int > [ n ]; for ( int i = 0 ; i < n ; i ++ ) L [ i ] = new List < int > (); // L[0] is equal to arr[0] L [ 0 ]. Add ( arr [ 0 ]); // start from index 1 for ( int i = 1 ; i < n ; i ++ ) { // for every j less than i for ( int j = 0 ; j < i ; j ++ ) { /* * L[i] = {MaxSum(L[j])} + arr[i] where j < i and arr[j] < arr[i] */ if (( arr [ i ] > arr [ j ]) && ( findSum ( L [ i ]) < findSum ( L [ j ]))) { foreach ( int k in L [ j ]) if ( ! L [ i ]. Contains ( k )) L [ i ] . Add ( k ); } } // L[i] ends with arr[i] L [ i ]. Add ( arr [ i ]); // L[i] now stores Maximum Sum Increasing // Subsequence of arr[0..i] that ends with // arr[i] } List < int > res = new List < int > ( L [ 0 ]); // res = L[0]; // find max foreach ( List < int > x in L ) if ( findSum ( x ) > findSum ( res )) res = x ; // max will contain result foreach ( int i in res ) Console . Write ( i + ' ' ); Console . WriteLine (); } // Driver Code public static void Main ( String [] args ) { int [] arr = { 3 2 6 4 5 1 }; int n = arr . Length ; // construct and print Max Sum IS of arr printMaxSumIs ( arr n ); } } // This code is contributed by PrinciRaj1992
' ); } // Driver Code let arr = [ 3 2 6 4 5 1 ]; let n = arr . length ; // construct and print Max Sum IS of arr printMaxSumIs ( arr n ); // This code is contributed by unknown2108 < /script>
Výstup3 4 5
Výše uvedené řešení DP můžeme optimalizovat odstraněním funkce findSum(). Místo toho můžeme udržovat další vektor/pole pro uložení součtu maximálního součtu rostoucí podsekvence, která končí arr[i].Časová složitost z výše uvedeného řešení dynamického programování je O(n 2 ).
Pomocný prostor používaný programem je O(n 2 ).Přístup 2: ( Použití Dynamické programování pomocí O(N) prostoru
Výše uvedený přístup se týkal toho, jak vytvořit subsekvenci zvyšující maximální součet v O(N 2 ) čas a O(N 2 ) prostor. V tomto přístupu optimalizujeme složitost prostoru a zkonstruujeme subsekvenci zvyšující maximální součet v O(N 2 ) čas a O(N) prostor.
- Nechť arr[0..n-1] je vstupní pole.
- Definujeme vektor párů L tak, že L[i] nejprve ukládá podposloupnost maximálního součtu arr[0..i], která končí arr[i] a L[i].second ukládá index předchozího prvku použitého pro generování součtu.
- Protože první prvek nemá žádný předchozí prvek, jeho index by byl -1 v L[0].
Například
array = [3 2 6 4 5 1]
L[0]: {3 -1}
L[1]: {2 1}
L[2]: {9 0}
L[3]: {7 0}
L[4]: {12 3}
L[5]: {1 5}Jak můžeme vidět výše, hodnota Maximum Sum Rostoucí Subsekvence je 12. Pro konstrukci aktuální Subsekvence použijeme index uložený v L[i].sekundě. Kroky k vytvoření Subsekvence jsou uvedeny níže:
- Ve vektorovém výsledku uložte hodnotu prvku, kde byla nalezena podsekvence zvyšující se maximální součet (tj. na currIndex = 4). Do výsledného vektoru tedy přidáme arr[currIndex].
- Aktualizujte currIndex na L[currIndex].second a opakujte krok 1, dokud currIndex nebude -1 nebo se nezmění (tj. currIndex == previousIndex).
- Zobrazte prvky výsledného vektoru v opačném pořadí.
Níže je uvedena implementace výše uvedené myšlenky:
C++14 /* Dynamic Programming solution to construct Maximum Sum Increasing Subsequence */ #include using namespace std ; // Function to construct and print the Maximum Sum // Increasing Subsequence void constructMaxSumIS ( vector < int > arr int n ) { // L[i] stores the value of Maximum Sum Increasing // Subsequence that ends with arr[i] and the index of // previous element used to construct the Subsequence vector < pair < int int > > L ( n ); int index = 0 ; for ( int i : arr ) { L [ index ] = { i index }; index ++ ; } // Set L[0].second equal to -1 L [ 0 ]. second = -1 ; // start from index 1 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 ] and L [ i ]. first < arr [ i ] + L [ j ]. first ) { L [ i ]. first = arr [ i ] + L [ j ]. first ; L [ i ]. second = j ; } } } int maxi = INT_MIN currIndex track = 0 ; for ( auto p : L ) { if ( p . first > maxi ) { maxi = p . first ; currIndex = track ; } track ++ ; } // Stores the final Subsequence vector < int > result ; // Index of previous element // used to construct the Subsequence int prevoiusIndex ; while ( currIndex >= 0 ) { result . push_back ( arr [ currIndex ]); prevoiusIndex = L [ currIndex ]. second ; if ( currIndex == prevoiusIndex ) break ; currIndex = prevoiusIndex ; } for ( int i = result . size () - 1 ; i >= 0 ; i -- ) cout < < result [ i ] < < ' ' ; } // Driver Code int main () { vector < int > arr = { 1 101 2 3 100 4 5 }; int n = arr . size (); // Function call constructMaxSumIS ( arr n ); return 0 ; }
Java // Dynamic Programming solution to construct // Maximum Sum Increasing Subsequence import java.util.* ; import java.awt.Point ; class GFG { // Function to construct and print the Maximum Sum // Increasing Subsequence static void constructMaxSumIS ( List < Integer > arr int n ) { // L.get(i) stores the value of Maximum Sum Increasing // Subsequence that ends with arr.get(i) and the index of // previous element used to construct the Subsequence List < Point > L = new ArrayList < Point > (); int index = 0 ; for ( int i : arr ) { L . add ( new Point ( i index )); index ++ ; } // Set L[0].second equal to -1 L . set ( 0 new Point ( L . get ( 0 ). x - 1 )); // Start from index 1 for ( int i = 1 ; i < n ; i ++ ) { // For every j less than i for ( int j = 0 ; j < i ; j ++ ) { if ( arr . get ( i ) > arr . get ( j ) && L . get ( i ). x < arr . get ( i ) + L . get ( j ). x ) { L . set ( i new Point ( arr . get ( i ) + L . get ( j ). x j )); } } } int maxi = - 100000000 currIndex = 0 track = 0 ; for ( Point p : L ) { if ( p . x > maxi ) { maxi = p . x ; currIndex = track ; } track ++ ; } // Stores the final Subsequence List < Integer > result = new ArrayList < Integer > (); // Index of previous element // used to construct the Subsequence int prevoiusIndex ; while ( currIndex >= 0 ) { result . add ( arr . get ( currIndex )); prevoiusIndex = L . get ( currIndex ). y ; if ( currIndex == prevoiusIndex ) break ; currIndex = prevoiusIndex ; } for ( int i = result . size () - 1 ; i >= 0 ; i -- ) System . out . print ( result . get ( i ) + ' ' ); } // Driver Code public static void main ( String [] s ) { List < Integer > arr = new ArrayList < Integer > (); arr . add ( 1 ); arr . add ( 101 ); arr . add ( 2 ); arr . add ( 3 ); arr . add ( 100 ); arr . add ( 4 ); arr . add ( 5 ); int n = arr . size (); // Function call constructMaxSumIS ( arr n ); } } // This code is contributed by rutvik_56
Python # Dynamic Programming solution to construct # Maximum Sum Increasing Subsequence import sys # Function to construct and print the Maximum Sum # Increasing Subsequence def constructMaxSumIS ( arr n ) : # L[i] stores the value of Maximum Sum Increasing # Subsequence that ends with arr[i] and the index of # previous element used to construct the Subsequence L = [] index = 0 for i in arr : L . append ([ i index ]) index += 1 # Set L[0].second equal to -1 L [ 0 ][ 1 ] = - 1 # start from index 1 for i in range ( 1 n ) : # for every j less than i for j in range ( i ) : if ( arr [ i ] > arr [ j ] and L [ i ][ 0 ] < arr [ i ] + L [ j ][ 0 ]) : L [ i ][ 0 ] = arr [ i ] + L [ j ][ 0 ] L [ i ][ 1 ] = j maxi currIndex track = - sys . maxsize 0 0 for p in L : if ( p [ 0 ] > maxi ) : maxi = p [ 0 ] currIndex = track track += 1 # Stores the final Subsequence result = [] while ( currIndex >= 0 ) : result . append ( arr [ currIndex ]) prevoiusIndex = L [ currIndex ][ 1 ] if ( currIndex == prevoiusIndex ) : break currIndex = prevoiusIndex for i in range ( len ( result ) - 1 - 1 - 1 ) : print ( result [ i ] end = ' ' ) arr = [ 1 101 2 3 100 4 5 ] n = len ( arr ) # Function call constructMaxSumIS ( arr n ) # This code is contributed by divyeshrabadiya07
C# /* Dynamic Programming solution to construct Maximum Sum Increasing Subsequence */ using System ; using System.Collections.Generic ; class GFG { // Function to construct and print the Maximum Sum // Increasing Subsequence static void constructMaxSumIS ( List < int > arr int n ) { // L[i] stores the value of Maximum Sum Increasing // Subsequence that ends with arr[i] and the index of // previous element used to construct the Subsequence List < Tuple < int int >> L = new List < Tuple < int int >> (); int index = 0 ; foreach ( int i in arr ) { L . Add ( new Tuple < int int > ( i index )); index ++ ; } // Set L[0].second equal to -1 L [ 0 ] = new Tuple < int int > ( L [ 0 ]. Item1 - 1 ); // start from index 1 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 ] && L [ i ]. Item1 < arr [ i ] + L [ j ]. Item1 ) { L [ i ] = new Tuple < int int > ( arr [ i ] + L [ j ]. Item1 j ); } } } int maxi = Int32 . MinValue currIndex = 0 track = 0 ; foreach ( Tuple < int int > p in L ) { if ( p . Item1 > maxi ) { maxi = p . Item1 ; currIndex = track ; } track ++ ; } // Stores the final Subsequence List < int > result = new List < int > (); // Index of previous element // used to construct the Subsequence int prevoiusIndex ; while ( currIndex >= 0 ) { result . Add ( arr [ currIndex ]); prevoiusIndex = L [ currIndex ]. Item2 ; if ( currIndex == prevoiusIndex ) break ; currIndex = prevoiusIndex ; } for ( int i = result . Count - 1 ; i >= 0 ; i -- ) Console . Write ( result [ i ] + ' ' ); } static void Main () { List < int > arr = new List < int > ( new int [] { 1 101 2 3 100 4 5 }); int n = arr . Count ; // Function call constructMaxSumIS ( arr n ); } } // This code is contributed by divyesh072019
JavaScript < script > // Dynamic Programming solution to construct // Maximum Sum Increasing Subsequence // Function to construct and print the Maximum Sum // Increasing Subsequence function constructMaxSumIS ( arr n ){ // L[i] stores the value of Maximum Sum Increasing // Subsequence that ends with arr[i] and the index of // previous element used to construct the Subsequence let L = [] let index = 0 for ( let i of arr ){ L . push ([ i index ]) index += 1 } // Set L[0].second equal to -1 L [ 0 ][ 1 ] = - 1 // start from index 1 for ( let i = 1 ; i < n ; i ++ ){ // for every j less than i for ( let j = 0 ; j < i ; j ++ ){ if ( arr [ i ] > arr [ j ] && L [ i ][ 0 ] < arr [ i ] + L [ j ][ 0 ]){ L [ i ][ 0 ] = arr [ i ] + L [ j ][ 0 ] L [ i ][ 1 ] = j } } } let maxi = Number . MIN_VALUE currIndex = 0 track = 0 for ( let p of L ){ if ( p [ 0 ] > maxi ){ maxi = p [ 0 ] currIndex = track } track += 1 } // Stores the final Subsequence let result = [] while ( currIndex >= 0 ){ result . push ( arr [ currIndex ]) let prevoiusIndex = L [ currIndex ][ 1 ] if ( currIndex == prevoiusIndex ) break currIndex = prevoiusIndex } for ( let i = result . length - 1 ; i >= 0 ; i -- ) document . write ( result [ i ] ' ' ) } let arr = [ 1 101 2 3 100 4 5 ] let n = arr . length // Function call constructMaxSumIS ( arr n ) // This code is contributed by shinjanpatra < /script>
Výstup
1 2 3 100
Časová náročnost: NA 2 )
Prostorová složitost: NA)
