Maximiza la puntuación multiplicando elementos de un Array dado con multiplicadores dados

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>
Producción

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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *