Maximizar la suma del producto de los elementos vecinos del elemento eliminado de Array

Dada una array A[] de tamaño N , la tarea es encontrar la puntuación máxima posible de esta array. La puntuación de una array se calcula realizando las siguientes operaciones en la array hasta que el tamaño de la array sea mayor que 2:

• Seleccione un índice i tal que   1 < i < N .
• Añade A[i-1] * A[i+1] a la partitura
• Quite A[i] de la array.

Ejemplo:

Entrada: A[] = {1, 2, 3, 4}
Salida: 12
Explicación:
En la primera operación, seleccione i = 2. La puntuación se incrementará en A[1] * A[3] = 2 * 4 = 8. La nueva array después de eliminar A[2] será {1, 2, 4}.
En la primera operación, seleccione i = 1. La puntuación aumentará en A[0] * A[2] = 1 * 4 = 4. La nueva array después de eliminar A[2] será {1, 4}.
Como N <= 2, no son posibles más operaciones. 
La puntuación total será 8 + 4 = 12, que es la máxima entre todas las opciones posibles.

Entrada: {1, 55}
Salida: 0
Explicación: No son posibles movimientos válidos.

Enfoque: El problema dado se puede resolver usando Programación Dinámica basada en las siguientes observaciones:

• Considere una array 2D, digamos dp[][] donde dp[i][j] representa la puntuación máxima posible en la subarreglo del índice i al j .
• Iterar sobre todos los subarreglos de longitudes len  en el rango [1, N-1] en orden creciente donde i denota el inicio yj denota el índice final del subarreglo de longitud actual.
• Se puede observar que para un subarreglo de i a j , el índice del último elemento restante k, distinto de i y j puede estar en el rango [i+1, j-1] . Por lo tanto, itere sobre todos los valores posibles de k . Por lo tanto, la relación DP se puede establecer de la siguiente manera:

dp[i][j] = max( dp[i][j], dp[i][k] + dp[k][j] + A[i]*A[j])   para todos los k en el rango [ i+1, j-1]

• La respuesta final será dp[0][N-1].

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores the dp state where dp[i][j]
// represents the maximum possible score
// in the subarray from index i to j
int dp[101][101];
 
// Function to calculate maximum possible
// score using the given operations
int maxMergingScore(int A[], int N)
{
    // Iterate through all possible
    // lengths of the subarray
    for (int len = 1; len < N; ++len) {
 
        // Iterate through all the
        // possible starting indices i
        // having length len
        for (int i = 0; i + len < N; ++i) {
 
            // Stores the rightmost index
            // of the current subarray
            int j = i + len;
 
            // Initial dp[i][j] will be 0.
            dp[i][j] = 0;
 
            // Iterate through all possible
            // values of k in range [i+1, j-1]
            for (int k = i + 1; k < j; ++k) {
                dp[i][j] = max(
                    dp[i][j],
                    dp[i][k] + dp[k][j]
                        + A[i] * A[j]);
            }
        }
    }
 
    // Return the answer
    return dp[0][N - 1];
}
 
// Driver Code
int main()
{
    int N = 4;
    int A[] = { 1, 2, 3, 4 };
 
    // Function Call
    cout << maxMergingScore(A, N) << endl;
 
    N = 2;
    int B[] = { 1, 55 };
 
    // Function Call
    cout << maxMergingScore(B, N) << endl;
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
 
  // Stores the dp state where dp[i][j]
  // represents the maximum possible score
  // in the subarray from index i to j
  static int maxMergingScore(int A[], int N)
  {
    int[][] dp = new int[101][101];
    for(int i = 0; i < 101; i++)
    {
      {
        for(int j = 0; j < 101; j++)
          dp[i][j] = 0;
      }
    }
 
    // Iterate through all possible
    // lengths of the subarray
    for (int len = 1; len < N; ++len) {
 
      // Iterate through all the
      // possible starting indices i
      // having length len
      for (int i = 0; i + len < N; ++i) {
 
        // Stores the rightmost index
        // of the current subarray
        int j = i + len;
 
        // Initial dp[i][j] will be 0.
        dp[i][j] = 0;
 
        // Iterate through all possible
        // values of k in range [i+1, j-1]
        for (int k = i + 1; k < j; ++k) {
          dp[i][j] = Math.max(
            dp[i][j],
            dp[i][k] + dp[k][j]
            + A[i] * A[j]);
        }
      }
    }
 
    // Return the answer
    return dp[0][N - 1];
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 4;
    int A[] = { 1, 2, 3, 4 };
 
    // Function Call
    System.out.println(maxMergingScore(A, N) );
 
    N = 2;
    int B[] = { 1, 55 };
 
    // Function Call
    System.out.println(maxMergingScore(B, N) );
  }
}
 
// This code is contributed by dwivediyash

// C# program for the above approach
using System;
 
public class GFG
{
 
  // Stores the dp state where dp[i][j]
  // represents the maximum possible score
  // in the subarray from index i to j
  static int maxMergingScore(int []A, int N)
  {
    int[,] dp = new int[101,101];
    for(int i = 0; i < 101; i++)
    {
      {
        for(int j = 0; j < 101; j++)
          dp[i, j] = 0;
      }
    }
 
    // Iterate through all possible
    // lengths of the subarray
    for (int len = 1; len < N; ++len) {
 
      // Iterate through all the
      // possible starting indices i
      // having length len
      for (int i = 0; i + len < N; ++i) {
 
        // Stores the rightmost index
        // of the current subarray
        int j = i + len;
 
        // Initial dp[i][j] will be 0.
        dp[i,j] = 0;
 
        // Iterate through all possible
        // values of k in range [i+1, j-1]
        for (int k = i + 1; k < j; ++k) {
          dp[i,j] = Math.Max(
            dp[i,j],
            dp[i,k] + dp[k,j]
            + A[i] * A[j]);
        }
      }
    }
 
    // Return the answer
    return dp[0,N - 1];
  }
 
  // Driver Code
    static public void Main (){
 
    int N = 4;
    int []A = { 1, 2, 3, 4 };
 
    // Function Call
    Console.WriteLine(maxMergingScore(A, N) );
 
    N = 2;
    int[] B = { 1, 55 };
 
    // Function Call
    Console.WriteLine(maxMergingScore(B, N) );
    }
}
 
// This code is contributed by maddler.

# Python 3 implementation for the above approach
 
# Stores the dp state where dp[i][j]
# represents the maximum possible score
# in the subarray from index i to j
 
# Function to calculate maximum possible
# score using the given operations
def maxMergingScore(A, N):
   
    # Iterate through all possible
    # len1gths of the subarray
    dp = [[0 for i in range(101)] for j in range(101)]
    for len1 in range(1,N,1):
       
        # Iterate through all the
        # possible starting indices i
        # having len1gth len1
        for i in range(0, N - len1, 1):
           
            # Stores the rightmost index
            # of the current subarray
            j = i + len1
 
            # Initial dp[i][j] will be 0.
            dp[i][j] = 0
 
            # Iterate through all possible
            # values of k in range [i+1, j-1]
            for k in range(i + 1, j, 1):
                dp[i][j] = max(dp[i][j],dp[i][k] + dp[k][j] + A[i] * A[j])
 
    # Return the answer
    return dp[0][N - 1]
 
# Driver Code
if __name__ == '__main__':
    N = 4
    A = [1, 2, 3, 4]
 
    # Function Call
    print(maxMergingScore(A, N))
 
    N = 2
    B = [1, 55]
 
    # Function Call
    print(maxMergingScore(B, N))
     
    # This code is contributed by SURENDRA_GANGWAR.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Stores the dp state where dp[i][j]
        // represents the maximum possible score
        // in the subarray from index i to j
        let dp = Array(101).fill().map(() => Array(101));
 
        // Function to calculate maximum possible
        // score using the given operations
        function maxMergingScore(A, N)
        {
         
            // Iterate through all possible
            // lengths of the subarray
            for (let len = 1; len < N; ++len) {
 
                // Iterate through all the
                // possible starting indices i
                // having length len
                for (let i = 0; i + len < N; ++i) {
 
                    // Stores the rightmost index
                    // of the current subarray
                    let j = i + len;
 
                    // Initial dp[i][j] will be 0.
                    dp[i][j] = 0;
 
                    // Iterate through all possible
                    // values of k in range [i+1, j-1]
                    for (let k = i + 1; k < j; ++k) {
                        dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i][k] + dp[k][j]
                            + A[i] * A[j]);
                    }
                }
            }
 
            // Return the answer
            return dp[0][N - 1];
        }
 
        // Driver Code
        let N = 4;
        let A = [1, 2, 3, 4];
 
        // Function Call
        document.write(maxMergingScore(A, N) + "<br>");
 
        N = 2;
        let B = [1, 55];
 
        // Function Call
        document.write(maxMergingScore(B, N) + "<br>");
 
// This code is contributed by Potta Lokesh
    </script>

12
0

Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(N ² )