Maximize the function by choosing Subsequence of size M
Given an array A[] with size N, Select a subsequence B = {B[1], B[2], B[3], ………B[N] } of size M from given array A[] (N ? M), the task is to find the maximum value of ? i * B[i] where i is from 1 to M.
The sequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.
Examples:
Input: A[] = {5, 4, -1, 8}, M = 2
Output: 21
Explanation: Choosing Subsequence B[] = {5, 8} from array A[] which has value ? i * B[i] = (1 * 5) + (2 * 8) = 21Input: A[] = {-3, 1, -4, 1, -5, 9, -2, 6, -5, 3}, M = 4
Output: 54
Explanation:
Choosing Subsequence B[] = {1, 1, 9, 6} from array A[] which has value ? i * B[i] = (1 * 1) + (2 * 1) + (3 * 9) + (4 * 6) = 54
Naive approach: The basic way to solve the problem is as follows:
Generating all subsequences of size M by recursive brute force and calculating their ? i * B[i] value and selecting maximum value.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem.
- dp[i][j] = X, represents the maximum value of ? i * B[i] by choosing j elements from first i elements of A[]
- recurrence relation : dp[i][j] = max(dp[i + 1][j + 1] + A[i] * j, dp[i + 1][j])
it can be observed that there are N * M states but the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of states. a This can be done using recursive string intact and just store the value in a HashMap and whenever the function is called, return the value tore without computing .
Follow the steps below to solve the problem:
- Create a recursive function that takes two parameters i representing the current index of A[] and j Number of elements already taken in subsequence B[].
- Call recursive function for both taking i’th element in subsequence B[] and not taking in Subsequence B[]
- Check the base case if exactly M elements are selected in subsequence then return 0 else return an invalid number.
- Create a 2d array of dp[N][M] by initializing all elements with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // dp table initialized with - 1 int dp[2001][2001]; // recursive function to calculate summation // of i * B[i] from 1 to M. int recur( int i, int j, int A[], int N, int M) { // base case if (i == N) { // if exactly subsequence of size M // selected then return 0. if (j == M + 1) return 0; // else return invalid number else return -1e9; } // if answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; int ans = INT_MIN; // calling recursive function to include // i'th array element of A[] in B[]. ans = max(ans, recur(i + 1, j + 1, A, N, M) + A[i] * j); // calling recursive function to not include // i'th array element of A[] in B[]. ans = max(ans, recur(i + 1, j, A, N, M)); // save and return dp value return dp[i][j] = ans; } // function to maximize summation of // i * B[i] for all i from 1 to M. void maximizeFunction( int A[], int N, int M) { // filling dp table with -1 memset (dp, -1, sizeof (dp)); cout << recur(0, 1, A, N, M) << endl; } // Driver Code int main() { // Input 1 int A[] = { 5, 4, -1, 8 }; int N = sizeof (A) / sizeof (A[0]); int M = 2; // Function Call maximizeFunction(A, N, M); // Input 2 int A1[] = { -3, 1, -4, 1, -5, 9, -2, 6, -5, 3 }; int N1 = sizeof (A1) / sizeof (A1[0]); int M1 = 4; // Function Call maximizeFunction(A1, N1, M1); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // dp table initialized with - 1 static int [][] dp = new int [ 2001 ][ 2001 ]; // recursive function to calculate summation // of i * B[i] from 1 to M. public static int recur( int i, int j, int [] A, int N, int M) { // base case if (i == N) { // if exactly subsequence of size M // selected then return 0. if (j == M + 1 ) return 0 ; // else return invalid number else return - 1000000 ; } // if answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != - 1 ) return dp[i][j]; int ans = Integer.MIN_VALUE; // calling recursive function to include // i'th array element of A[] in B[]. ans = Math.max(ans, recur(i + 1 , j + 1 , A, N, M) + A[i] * j); // calling recursive function to not include // i'th array element of A[] in B[]. ans = Math.max(ans, recur(i + 1 , j, A, N, M)); // save and return dp value return dp[i][j] = ans; } // function to maximize summation of // i * B[i] for all i from 1 to M. public static void maximizeFunction( int [] A, int N, int M) { // filling dp table with -1 for ( int i = 0 ; i < dp.length; i++) { Arrays.fill(dp[i], - 1 ); } System.out.println(recur( 0 , 1 , A, N, M)); } public static void main(String[] args) { // Input 1 int [] A = { 5 , 4 , - 1 , 8 }; int N = A.length; int M = 2 ; // Function Call maximizeFunction(A, N, M); // Input 2 int [] A1 = { - 3 , 1 , - 4 , 1 , - 5 , 9 , - 2 , 6 , - 5 , 3 }; int N1 = A1.length; int M1 = 4 ; // Function Call maximizeFunction(A1, N1, M1); } } // This code is contributed by lokesh. |
Python3
# Python code for the above approach # dp table initialized with - 1 dp = [[ - 1 ] * 2001 for _ in range ( 2001 )] # recursive function to calculate summation # of i * B[i] from 1 to M. def recur(i, j, A, N, M): # base case if i = = N: # if exactly subsequence of size M # selected then return 0. if j = = M + 1 : return 0 # else return invalid number else : return - 1e9 # if answer for current state is already # calculated then just return dp[i][j] if dp[i][j] ! = - 1 : return dp[i][j] ans = float ( "-inf" ) # calling recursive function to include # i'th array element of A[] in B[]. ans = max (ans, recur(i + 1 , j + 1 , A, N, M) + A[i] * j) # calling recursive function to not include # i'th array element of A[] in B[]. ans = max (ans, recur(i + 1 , j, A, N, M)) # save and return dp value dp[i][j] = ans return ans # function to maximize summation of # i * B[i] for all i from 1 to M. def maximize_function(A, N, M): # filling dp table with -1 for i in range ( 2001 ): for j in range ( 2001 ): dp[i][j] = - 1 print (recur( 0 , 1 , A, N, M)) # Driver Code # Input 1 A = [ 5 , 4 , - 1 , 8 ] N = len (A) M = 2 # Function Call maximize_function(A, N, M) # Input 2 A1 = [ - 3 , 1 , - 4 , 1 , - 5 , 9 , - 2 , 6 , - 5 , 3 ] N1 = len (A1) M1 = 4 # Function Call maximize_function(A1, N1, M1) # This code is contributed by Potta Lokesh |
C#
using System; using System.Linq; class GFG { // dp table initialized with - 1 static int [,] dp= new int [2001, 2001]; // recursive function to calculate summation // of i * B[i] from 1 to M. static int recur( int i, int j, int [] A, int N, int M) { // base case if (i == N) { // if exactly subsequence of size M // selected then return 0. if (j == M + 1) return 0; // else return invalid number else return -1000000000; } // if answer for current state is already // calculated then just return dp[i][j] if (dp[i,j] != -1) return dp[i,j]; int ans = -2147483648; // calling recursive function to include // i'th array element of A[] in B[]. ans = Math.Max(ans, recur(i + 1, j + 1, A, N, M) + A[i] * j); // calling recursive function to not include // i'th array element of A[] in B[]. ans = Math.Max(ans, recur(i + 1, j, A, N, M)); // save and return dp value return dp[i,j] = ans; } // function to maximize summation of // i * B[i] for all i from 1 to M. static void maximizeFunction( int [] A, int N, int M) { // filling dp table with -1 for ( int i=0; i<2001; i++) { for ( int j=0; j<2001; j++) dp[i,j]=-1; } Console.Write(recur(0, 1, A, N, M)+ "\n" ); } // Driver Code public static void Main( string [] args) { // Input 1 int [] A = { 5, 4, -1, 8 }; int N = A.Length; int M = 2; // Function Call maximizeFunction(A, N, M); // Input 2 int [] A1 = { -3, 1, -4, 1, -5, 9, -2, 6, -5, 3 }; int N1 = A1.Length; int M1 = 4; // Function Call maximizeFunction(A1, N1, M1); } } // This code is contributed by ratiagarwal. |
Javascript
// Javascript code to implement the approach // dp table initialized with - 1 let dp = new Array(2001); // recursive function to calculate summation // of i * B[i] from 1 to M. function recur(i, j, A, N, M) { // base case if (i == N) { // if exactly subsequence of size M // selected then return 0. if (j == M + 1) return 0; // else return invalid number else return -1e9; } // if answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; let ans = Number.MIN_SAFE_INTEGER; // calling recursive function to include // i'th array element of A[] in B[]. ans = Math.max(ans, recur(i + 1, j + 1, A, N, M) + A[i] * j); // calling recursive function to not include // i'th array element of A[] in B[]. ans = Math.max(ans, recur(i + 1, j, A, N, M)); // save and return dp value return dp[i][j] = ans; } // function to maximize summation of // i * B[i] for all i from 1 to M. function maximizeFunction(A, N, M) { // filling dp table with -1 for (let i=0; i<2001; i++) dp[i]= new Array(2001).fill(-1); document.write(recur(0, 1, A, N, M)); } // Driver Code // Input 1 let A = [ 5, 4, -1, 8 ]; let N = A.length; let M = 2; // Function Call maximizeFunction(A, N, M); // Input 2 let A1 = [ -3, 1, -4, 1, -5, 9, -2, 6, -5, 3 ]; let N1 = A1.length; let M1 = 4; // Function Call maximizeFunction(A1, N1, M1); |
21 54
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Approach 2: Using Tabulation (Space Optimized – No Stack Space required)
The code uses dynamic programming to find the maximum summation of i * B[i] for given constraints.
- It initializes a DP table dp with dimensions (N + 1) x (M + 1) and initializes all elements to -INF.
- Base case: If no elements are selected (j is 0), the sum is 0.
- The nested loops update dp by considering two possibilities:
- Including the current element in subsequence B.
- Not including the current element in subsequence B.
- The maximum value is chosen between these two possibilities.
- The final answer is in dp[N][M].
Here is the implementation of above approach in C++.
C++
// C++ Implementation of the tabulation dp approach #include <iostream> #include <vector> using namespace std; const int INF = 1e9; // A large invalid number int maximizeFunction( int A[], int N, int M) { vector<vector< int >> dp(N + 1, vector< int >(M + 1, -INF)); // Base case: If no elements are selected, the sum is 0. for ( int i = 0; i <= N; i++) { dp[i][0] = 0; } for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= M; j++) { // Include the current element in subsequence B dp[i][j] = dp[i - 1][j - 1] + A[i - 1] * j; // Don't include the current element in subsequence B dp[i][j] = max(dp[i][j], dp[i - 1][j]); } } // The answer will be in dp[N][M] return dp[N][M]; } int main() { // Input 1 int A[] = {5, 4, -1, 8}; int N = sizeof (A) / sizeof (A[0]); int M = 2; cout << maximizeFunction(A, N, M) << endl; // Input 2 int A1[] = {-3, 1, -4, 1, -5, 9, -2, 6, -5, 3}; int N1 = sizeof (A1) / sizeof (A1[0]); int M1 = 4; cout << maximizeFunction(A1, N1, M1) << endl; return 0; } // This code is contributed by Tapesh(tapeshdua420) |
Java
import java.util.Arrays; public class TabulationDP { static final int INF = 1000000000 ; // A large invalid number static int maximizeFunction( int [] A, int N, int M) { int [][] dp = new int [N + 1 ][M + 1 ]; // Initialize the dp array with -INF for ( int i = 0 ; i <= N; i++) { Arrays.fill(dp[i], -INF); } // Base case: If no elements are selected, the sum is 0. for ( int i = 0 ; i <= N; i++) { dp[i][ 0 ] = 0 ; } for ( int i = 1 ; i <= N; i++) { for ( int j = 1 ; j <= M; j++) { // Include the current element in subsequence B dp[i][j] = dp[i - 1 ][j - 1 ] + A[i - 1 ] * j; // Don't include the current element in subsequence B dp[i][j] = Math.max(dp[i][j], dp[i - 1 ][j]); } } // The answer will be in dp[N][M] return dp[N][M]; } public static void main(String[] args) { // Input 1 int [] A = { 5 , 4 , - 1 , 8 }; int N = A.length; int M = 2 ; System.out.println(maximizeFunction(A, N, M)); // Input 2 int [] A1 = {- 3 , 1 , - 4 , 1 , - 5 , 9 , - 2 , 6 , - 5 , 3 }; int N1 = A1.length; int M1 = 4 ; System.out.println(maximizeFunction(A1, N1, M1)); } } // This is contributed by Ashish |
Python3
# Python Implementation of the tabulation dp approach INF = 10 * * 9 # A large invalid number def maximize_function(A, N, M): # Initialize a 2D list for dynamic programming dp = [[ - INF] * (M + 1 ) for _ in range (N + 1 )] # Base case: If no elements are selected, the sum is 0. for i in range (N + 1 ): dp[i][ 0 ] = 0 for i in range ( 1 , N + 1 ): for j in range ( 1 , M + 1 ): # Include the current element in subsequence B dp[i][j] = dp[i - 1 ][j - 1 ] + A[i - 1 ] * j # Don't include the current element in subsequence B dp[i][j] = max (dp[i][j], dp[i - 1 ][j]) # The answer will be in dp[N][M] return dp[N][M] # Driver code # Input 1 A = [ 5 , 4 , - 1 , 8 ] N = len (A) M = 2 print (maximize_function(A, N, M)) # Input 2 A1 = [ - 3 , 1 , - 4 , 1 , - 5 , 9 , - 2 , 6 , - 5 , 3 ] N1 = len (A1) M1 = 4 print (maximize_function(A1, N1, M1)) |
C#
using System; class Program { const int INF = 1000000000; // A large invalid number static int MaximizeFunction( int [] A, int N, int M) { int [,] dp = new int [N + 1, M + 1]; // Base case: If no elements are selected, the sum is 0. for ( int i = 0; i <= N; i++) { dp[i, 0] = 0; } for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= M; j++) { // Include the current element in subsequence B dp[i, j] = dp[i - 1, j - 1] + A[i - 1] * j; // Don't include the current element in subsequence B dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j]); } } // The answer will be in dp[N, M] return dp[N, M]; } static void Main() { // Input 1 int [] A = { 5, 4, -1, 8 }; int N = A.Length; int M = 2; Console.WriteLine(MaximizeFunction(A, N, M)); // Input 2 int [] A1 = { -3, 1, -4, 1, -5, 9, -2, 6, -5, 3 }; int N1 = A1.Length; int M1 = 4; Console.WriteLine(MaximizeFunction(A1, N1, M1)); } } |
Javascript
const INF = 1e9; // A large invalid number function maximizeFunction(A, N, M) { const dp = Array.from({ length: N + 1 }, () => Array(M + 1).fill(-INF)); // Base case: If no elements are selected, the sum is 0. for (let i = 0; i <= N; i++) { dp[i][0] = 0; } for (let i = 1; i <= N; i++) { for (let j = 1; j <= M; j++) { // Include the current element in subsequence B dp[i][j] = dp[i - 1][j - 1] + A[i - 1] * j; // Don't include the current element in subsequence B dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); } } // The answer will be in dp[N][M] return dp[N][M]; } // Input 1 const A = [5, 4, -1, 8]; const N = A.length; const M = 2; console.log(maximizeFunction(A, N, M)); // Input 2 const A1 = [-3, 1, -4, 1, -5, 9, -2, 6, -5, 3]; const N1 = A1.length; const M1 = 4; console.log(maximizeFunction(A1, N1, M1)); |
21 54
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Related Articles :
Contact Us