Dadas dos arrays array[] y multiplicadores[] de tamaño N y M donde N siempre es mayor que igual a M. Hay M operaciones a realizar. En cada operación, elija el multiplicador[i] y un elemento de la array arr[], ya sea desde el principio o el final, digamos K , luego agregue el multiplicador[i]*K al puntaje total, digamos, y elimine K de la array arr[ ]. La tarea es encontrar el valor máximo de la puntuación final ans.
Ejemplos:
Entrada : array[] = {1, 2, 3}, multiplicadores[] = {3, 2, 1}, N=3, M=3
Salida : 14
Explicación : una solución óptima es la siguiente:
– Elija del final , [1, 2, 3], sumando 3 * 3 = 9 a la puntuación.
– Elige del final, [1, 2], sumando 2 * 2 = 4 a la puntuación.
– Elija del final, [1], sumando 1 * 1 = 1 a la puntuación.
La puntuación total es 9 + 4 + 1 = 14.Entrada: array[] = {2, 1}, multiplicadores[] = {0}, N=2, M=1
Salida: 0
Explicación: No importa si se elige 2 o 1, la respuesta será 0 porque multiplicador[0] es igual a 0
Enfoque ingenuo: la solución de fuerza bruta es verificar todos y cada uno de los pares recursivamente y encontrar la solución óptima.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum score // using dynamic programming and // memoization int 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); return 0; } // This code is contributed by rakeshsahni
Java
// Java program for the above approach 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 AnkThon
Python3
# Python program for the above approach # Function to find the maximum score # recursively def 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 Code if __name__ == "__main__": array = [1, 2, 3] multipliers = [3, 2, 1] print(getMaxScore(array, multipliers))
C#
// C# program for the above approach using 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 // memoization function 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 Code let array = [1, 2, 3]; let multipliers = [3, 2, 1]; document.write(getMaxScore(array, multipliers)); // This code is contributed by gfgking </script>
14
Tiempo Complejidad: O(2 M )
Espacio Auxiliar: O(1)
Enfoque eficiente: la solución se basa en la programación dinámica, ya que contiene ambas propiedades: subestructura óptima y subproblemas superpuestos . Suponga que dp[i][j] es el resultado máximo actual que se puede obtener de un subarreglo, donde i es el índice inicial y j es el final. En cualquier etapa, hay dos opciones:
elige el primero: dp[i + 1][j] + curr_weight * array[i]
elige el último: dp[i][j – 1] + curr_weight * array[j]
El resultado será el máximo de ambos. Siga los pasos a continuación para resolver el problema utilizando la búsqueda y memorización en profundidad :
- Inicializar una variable permanece como NM .
- Inicialice una array dp[] de tamaño M+1 con valores 0.
- Iterar sobre el rango [0, M) usando la variable i y realizar los siguientes pasos:
- Inicializa una variable mm como multiplicadores[-i-1] .
- Iterar sobre el rango [0, Mi) usando la variable j y realizar los siguientes pasos:
- Establezca el valor de dp[j] como el máximo de mm*array[j] + dp[j+1] o mm*array[j+remain] + dp[j].
- Aumenta el valor de permanecer en 1.
- Después de realizar los pasos anteriores, imprima el valor de dp[0] como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// Java program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum score // using dynamic programming and // memoization int 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 approach import 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 # memoization def 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 Code if __name__ == "__main__": array = [1, 2, 3] multipliers = [3, 2, 1] print(getMaxScore(array, multipliers))
C#
// C# program for the above approach using 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>
14
Complejidad temporal: O(M*M)
Espacio auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por maheswaripiyush9 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA