Producto máximo del par restante después de reemplazar repetidamente pares de elementos de array adyacentes con su suma

Dada una array arr[] de tamaño N , la tarea es encontrar el producto máximo posible de los pares restantes después de reemplazar repetidamente un par de elementos de array adyacentes con su suma. 

Nota: Reduzca la array a un tamaño de 2.

Ejemplos:

Entrada: arr[] = {2, 3, 5, 6, 7}
Salida: 130
Explicación:
Reemplazar arr[1] y arr[2] con su suma (es decir, 3 + 5 = 8) modifica arr[] a {2 , 8, 6, 7}
Reemplazar arr[2] y arr[3] con su suma (es decir, 6 + 7 = 13) modifica arr[] a {2, 8, 13} Reemplazar arr[0]
y arr[1] con su suma (2 + 8 = 10) modifica arr[] a {10, 13}
Producto Máximo del par restante = 10 * 13 = 130

Entrada: arr[] = {5, 6}
Salida: 30

Enfoque: El problema dado se puede resolver mediante la observación. Se puede observar que para un índice i , X debe ser igual a la suma de los primeros i elementos, es decir, arr[1] + arr[2] + arr[3] + … + arr[i] e Y debe ser igual a la suma del resto de los elementos, es decir, arr[i + 1] + arr[i + 2] +…+ arr[N]. Ahora, el problema se puede resolver usando el prefijo sum y encontrando el producto con la suma del resto de los elementos en cada índice. Siga los pasos a continuación para resolver el problema:

• Inicialice ans como INT_MIN para almacenar la respuesta requerida y prefixSum como 0 para almacenar la suma de prefijos de la array.
• Almacene la suma total de los elementos de la array en una variable, digamos S .
• Recorra la array sobre el rango de índices [0, N – 2] usando la variable i y realice las siguientes operaciones:
  • Agrega el valor de arr[i] a prefixSum .
  • Almacene el valor de prefixSum en una variable X y almacene (sum – prefixSum) en una variable Y.
  • Si el valor de (X * Y) es mayor que ans , actualice ans como (X * Y) .
• Después de completar los pasos anteriores, imprima el valor de ans como resultado.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum product
// possible after repeatedly replacing
// pairs of adjacent array elements
// with their sum
void maxProduct(int arr[], int N)
{
    // Store the maximum product
    int max_product = INT_MIN;
 
    // Store the prefix sum
    int prefix_sum = 0;
 
    // Store the total sum of array
    int sum = 0;
 
    // Traverse the array to find
    // the total sum
    for (int i = 0; i < N; i++) {
        sum += arr[i];
    }
 
    // Iterate in the range [0, N-2]
    for (int i = 0; i < N - 1; i++) {
 
        // Add arr[i] to prefix_sum
        prefix_sum += arr[i];
 
        // Store the value of prefix_sum
        int X = prefix_sum;
 
        // Store the value of
        // (total sum - prefix sum)
        int Y = sum - prefix_sum;
 
        // Update the maximum product
        max_product = max(max_product,
                          X * Y);
    }
 
    // Print the answer
    cout << max_product;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 3, 5, 6, 7 };
    int N = sizeof(arr) / sizeof(arr[0]);
    maxProduct(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
  // Function to find the maximum product
  // possible after repeatedly replacing
  // pairs of adjacent array elements
  // with their sum
  static void maxProduct(int[] arr, int N)
  {
    // Store the maximum product
    int max_product = Integer.MIN_VALUE;
 
    // Store the prefix sum
    int prefix_sum = 0;
 
    // Store the total sum of array
    int sum = 0;
 
    // Traverse the array to find
    // the total sum
    for (int i = 0; i < N; i++)
    {
      sum += arr[i];
    }
 
    // Iterate in the range [0, N-2]
    for (int i = 0; i < N - 1; i++)
    {
 
      // Add arr[i] to prefix_sum
      prefix_sum += arr[i];
 
      // Store the value of prefix_sum
      int X = prefix_sum;
 
      // Store the value of
      // (total sum - prefix sum)
      int Y = sum - prefix_sum;
 
      // Update the maximum product
      max_product = Math.max(max_product, X * Y);
    }
 
    // Print the answer
    System.out.print(max_product);
  }
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 2, 3, 5, 6, 7 };
    int N = arr.length;
    maxProduct(arr, N);
}
}
 
// This code is contributed by sanjoy_62.

# Python program for the above approach
import sys
 
# Function to find the maximum product
# possible after repeatedly replacing
# pairs of adjacent array elements
# with their sum
def maxProduct(arr, N):
   
    # Store the maximum product
    max_product = -sys.maxsize;
 
    # Store the prefix sum
    prefix_sum = 0;
 
    # Store the total sum of array
    sum = 0;
 
    # Traverse the array to find
    # the total sum
    for i in range(N):
        sum += arr[i];
 
    # Iterate in the range [0, N-2]
    for i in range(N - 1):
       
        # Add arr[i] to prefix_sum
        prefix_sum += arr[i];
 
        # Store the value of prefix_sum
        X = prefix_sum;
 
        # Store the value of
        # (total sum - prefix sum)
        Y = sum - prefix_sum;
 
        # Update the maximum product
        max_product = max(max_product, X * Y);
 
    # Print the answer
    print(max_product);
 
# Driver Code
if __name__ == '__main__':
    arr = [2, 3, 5, 6, 7];
    N = len(arr);
    maxProduct(arr, N);
 
# This code is contributed by shikhasingrajput

// C# program for the above approach
using System;
class GFG
{
 
  // Function to find the maximum product
  // possible after repeatedly replacing
  // pairs of adjacent array elements
  // with their sum
  static void maxProduct(int[] arr, int N)
  {
    // Store the maximum product
    int max_product = Int32.MinValue;
 
    // Store the prefix sum
    int prefix_sum = 0;
 
    // Store the total sum of array
    int sum = 0;
 
    // Traverse the array to find
    // the total sum
    for (int i = 0; i < N; i++)
    {
      sum += arr[i];
    }
 
    // Iterate in the range [0, N-2]
    for (int i = 0; i < N - 1; i++)
    {
 
      // Add arr[i] to prefix_sum
      prefix_sum += arr[i];
 
      // Store the value of prefix_sum
      int X = prefix_sum;
 
      // Store the value of
      // (total sum - prefix sum)
      int Y = sum - prefix_sum;
 
      // Update the maximum product
      max_product = Math.Max(max_product, X * Y);
    }
 
    // Print the answer
    Console.WriteLine(max_product);
  } 
 
  // Driver code
  static void Main()
  {
    int[] arr = { 2, 3, 5, 6, 7 };
    int N = arr.Length;
    maxProduct(arr, N);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
// javascript program for the above approach
 
    // Function to find the maximum product
    // possible after repeatedly replacing
    // pairs of adjacent array elements
    // with their sum
    function maxProduct(arr , N) {
        // Store the maximum product
        var max_product = Number.MIN_VALUE;
 
        // Store the prefix sum
        var prefix_sum = 0;
 
        // Store the total sum of array
        var sum = 0;
 
        // Traverse the array to find
        // the total sum
        for (i = 0; i < N; i++) {
            sum += arr[i];
        }
 
        // Iterate in the range [0, N-2]
        for (i = 0; i < N - 1; i++) {
 
            // Add arr[i] to prefix_sum
            prefix_sum += arr[i];
 
            // Store the value of prefix_sum
            var X = prefix_sum;
 
            // Store the value of
            // (total sum - prefix sum)
            var Y = sum - prefix_sum;
 
            // Update the maximum product
            max_product = Math.max(max_product, X * Y);
        }
 
        // Print the answer
        document.write(max_product);
    }
 
    // Driver Code
     
        var arr = [ 2, 3, 5, 6, 7 ];
        var N = arr.length;
        maxProduct(arr, N);
 
// This code contributed by umadevi9616
</script>

130

Complejidad temporal: O(N)
Espacio auxiliar: O(1)