Given two arrays array[] and multipliers[] of size N and M where N is always greater than equal to M. There are M operations to be performed. In each operation, choose multiplier[i] and an element from the array arr[] either from the start or the end let’s say K then add multiplier[i]*K to the total score say ans and remove K from the array arr[]. The task is to find the maximum value of the final score ans.
Examples:
Input: array[] = {1, 2, 3}, multipliers[] = {3, 2, 1}, N=3, M=3
Output: 14
Explanation: An optimal solution is as follows:
– Choose from the end, [1, 2, 3], adding 3 * 3 = 9 to the score.
– Choose from the end, [1, 2], adding 2 * 2 = 4 to the score.
– Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.Input: array[] = {2, 1}, multipliers[] = {0}, N=2, M=1
Output: 0
Explanation: No matter 2 or 1 is chosen, the answer will be 0 because multiplier[0] equals 0.
Naive Approach: The brute force solution is to check each and every pair recursively and find the optimal solution.
Below is the implementation of the above approach
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum score// using dynamic programming and// memoizationint getMaxScore(vector<int>& array, vector<int>& multipliers){ // M is the number of elements needed to pick int M = multipliers.size(), N = array.size(); int remain = N - M; vector<int> dp(M + 1, 0); for (int i = 0; i < M; ++i) { int mm = multipliers[M - i - 1]; for (int j = 0; j < M - i; ++j) { dp[j] = max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]); } remain += 1; } return dp[0];}// Driver Codeint main(){ vector<int> array = { 1, 2, 3 }; vector<int> multipliers = { 3, 2, 1 }; cout << getMaxScore(array, multipliers); return 0;}// This code is contributed by rakeshsahni |
Java
// Java program for the above approachpublic class GFG { // Function to find the maximum score // using dynamic programming and // memoization static int getMaxScore(int []array,int []multipliers) { // M is the number of elements needed to pick int M = multipliers.length; int N = array.length; int remain = N - M; int dp[] = new int[M + 1]; for (int i = 0; i < M; ++i) { int mm = multipliers[M - i - 1]; for (int j = 0; j < M - i; ++j) { dp[j] = Math.max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]); } remain += 1; } return dp[0]; } // Driver Code public static void main (String[] args) { int []array = { 1, 2, 3 }; int []multipliers = { 3, 2, 1 }; System.out.println(getMaxScore(array, multipliers)); }}// This code is contributed by AnkThon |
Python3
# Python program for the above approach# Function to find the maximum score# recursivelydef getMaxScore(array, multipliers): # Depth first search def dfs(start, end, index): if index == len(multipliers): return 0 # Pick left left = multipliers[index] * array[start] + \ dfs(start + 1, end, index + 1) # Pick right right = multipliers[index] * array[end] + \ dfs(start, end - 1, index + 1) return max(right, left) return dfs(0, len(array) - 1, 0)# Driver Codeif __name__ == "__main__": array = [1, 2, 3] multipliers = [3, 2, 1] print(getMaxScore(array, multipliers)) |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the maximum score // using dynamic programming and // memoization static int getMaxScore(int[] array, int[] multipliers) { // M is the number of elements needed to pick int M = multipliers.Length; int N = array.Length; int remain = N - M; int[] dp = new int[M + 1]; for (int i = 0; i < M; ++i) { int mm = multipliers[M - i - 1]; for (int j = 0; j < M - i; ++j) { dp[j] = Math.Max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]); } remain += 1; } return dp[0]; } // Driver Code public static void Main(String[] args) { int[] array = { 1, 2, 3 }; int[] multipliers = { 3, 2, 1 }; Console.Write(getMaxScore(array, multipliers)); }}// This code is contributed by gfgking. |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum score// using dynamic programming and// memoizationfunction getMaxScore(array, multipliers) { // M is the number of elements needed to pick let M = multipliers.length, N = array.length; let remain = N - M; let dp = new Array(M + 1).fill(0); for (let i = 0; i < M; ++i) { let mm = multipliers[M - i - 1]; for (let j = 0; j < M - i; ++j) { dp[j] = Math.max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]); } remain += 1; } return dp[0];}// Driver Codelet array = [1, 2, 3];let multipliers = [3, 2, 1];document.write(getMaxScore(array, multipliers));// This code is contributed by gfgking</script> |
Output
14
Time Complexity: O(2M)
Auxiliary Space: O(M)
Efficient Approach: The solution is based on dynamic programming as it contains both the properties – optimal substructure and overlapping subproblems. Assume dp[i][j] is the current maximum result that can get from a subarray, where i is the start index and j is the end. At any stage, there are two choices:
pick the first: dp[i + 1][j] + curr_weight * array[i]
pick the last: dp[i][j – 1] + curr_weight * array[j]
The result will be the maximum of both. Follow the steps below to solve the problem using depth-first search and memorization:
- Initialize a variable remain as N-M.
- Initialize an array dp[] of size M+1 with values 0.
- Iterate over the range [0, M) using the variable i and perform the following steps:
- Initialize a variable mm as multipliers[-i-1].
- Iterate over the range [0, M-i) using the variable j and perform the following steps:
- Set the value of dp[j] as the maximum of mm*array[j] + dp[j+1] or mm*array[j+remain] + dp[j].
- Increase the value of remain by 1.
- After performing the above steps, print the value of dp[0] as the answer.
Below is the implementation of the above approach:
C++
// Java program for the above approach#include <bits/stdc++.h>using namespace std; // Function to find the maximum score // using dynamic programming and // memoizationint getMaxScore(vector<int>& array, vector<int>& multipliers){ // M is the number of elements needed to pick int M = multipliers.size(), N = array.size(); int remain = N - M; vector<int> dp(M + 1, 0); for (int i = 0; i < M; ++i) { int mm = multipliers[M - i - 1]; for (int j = 0; j < M - i; ++j) { dp[j] = max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]); } remain += 1; } return dp[0]; } // Driver Code int main () { vector<int> array = { 1, 2, 3 }; vector<int> multipliers = { 3, 2, 1 }; cout << getMaxScore(array, multipliers); }// This code is contributed by shikhasingrajput |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Function to find the maximum score // using dynamic programming and // memoization static int getMaxScore(int []array,int []multipliers) { // M is the number of elements needed to pick int M = multipliers.length; int N = array.length; int remain = N - M; int dp[] = new int[M + 1]; for (int i = 0; i < M; ++i) { int mm = multipliers[M - i - 1]; for (int j = 0; j < M - i; ++j) { dp[j] = Math.max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]); } remain += 1; } return dp[0]; } // Driver Code public static void main (String[] args) { int []array = { 1, 2, 3 }; int []multipliers = { 3, 2, 1 }; System.out.println(getMaxScore(array, multipliers)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for the above approach# Function to find the maximum score# using dynamic programming and# memoizationdef getMaxScore(array, multipliers): # M is the number of elements needed to pick M, N = len(multipliers), len(array) remain = N - M dp = [0] * (M + 1) for i in range(M): mm = multipliers[-i - 1] for j in range(M - i): dp[j] = max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]) remain += 1 return dp[0]# Driver Codeif __name__ == "__main__": array = [1, 2, 3] multipliers = [3, 2, 1] print(getMaxScore(array, multipliers)) |
C#
// C# program for the above approachusing System;public class GFG { // Function to find the maximum score // using dynamic programming and // memoization static int getMaxScore(int[] array, int[] multipliers) { // M is the number of elements needed to pick int M = multipliers.Length; int N = array.Length; int remain = N - M; int[] dp = new int[M + 1]; for (int i = 0; i < M; ++i) { int mm = multipliers[M - i - 1]; for (int j = 0; j < M - i; ++j) { dp[j] = Math.Max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]); } remain += 1; } return dp[0]; } // Driver Code public static void Main(string[] args) { int[] array = { 1, 2, 3 }; int[] multipliers = { 3, 2, 1 }; Console.WriteLine(getMaxScore(array, multipliers)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach //Function to find the maximum score //using dynamic programming and //memoization function getMaxScore(array, multipliers) { //M is the number of elements needed to pick M = multipliers.length N = array.length remain = N - M dp = new Array(M + 1).fill(0) for (let i = 0; i < M; i++) { mm = multipliers[M - i - 1] for (j = 0; j < M - i; j++) dp[j] = Math.max(mm * array[j] + dp[j + 1], mm * array[j + remain] + dp[j]) remain += 1 } return dp[0] } array = [1, 2, 3] multipliers = [3, 2, 1] document.write(getMaxScore(array, multipliers)) // This code is contributed by Potta Lokesh </script> |
Output
14
Time Complexity: O(M*M)
Auxiliary Space: O(M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!