Producto máximo de la suma de dos subarreglos contiguos de un arreglo

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros positivos, la tarea es dividir la array en dos subarreglos contiguos de modo que el producto de la suma de dos subarreglos contiguos sea máximo. 

Ejemplos: 

Entrada: arr[] = {4, 10, 1, 7, 2, 9} 
Salida: 270 
Todas las particiones posibles y su producto de suma son: 
{4} y {10, 1, 7, 2, 9} -> producto de suma = 116 
{4, 10} y {1, 7, 2, 9} -> producto de suma = 266 
{4, 10, 1} y {7, 2, 9} -> producto de suma = 270 
{4 , 10, 1, 7} y {2, 9} -> producto de suma = 242 
{4, 10, 1, 7, 2} y {9} -> producto de suma = 216

Entrada: arr[] = {4, 10, 11, 10, 4} 
Salida: 350 

Enfoque ingenuo: un enfoque simple es considerar todas las particiones posibles para los subarreglos uno por uno y calcular el producto máximo de la suma de los subarreglos.
A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum
// product of sum for any partition
int maxProdSum(int arr[], int n)
{
    int leftArraySum = 0, maxProduct = 0;
 
    // Traversing the array
    for (int i = 0; i < n; i++) {
 
        // Compute left array sum
        leftArraySum += arr[i];
 
        // Compute right array sum
        int rightArraySum = 0;
        for (int j = i + 1; j < n; j++) {
            rightArraySum += arr[j];
        }
 
        // Multiplying left and right subarray sum
        int k = leftArraySum * rightArraySum;
 
        // Checking for the maximum product
        // of sum of left and right subarray
        if (k > maxProduct) {
            maxProduct = k;
        }
    }
 
    // Printing the maximum product
    return maxProduct;
}
 
// Driver code
int main()
{
    int arr[] = { 4, 10, 1, 7, 2, 9 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << maxProdSum(arr, n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
// Function to return the maximum
// product of sum for any partition
static int maxProdSum(int arr[], int n)
{
    int leftArraySum = 0, maxProduct = 0;
 
    // Traversing the array
    for (int i = 0; i < n; i++)
    {
 
        // Compute left array sum
        leftArraySum += arr[i];
 
        // Compute right array sum
        int rightArraySum = 0;
        for (int j = i + 1; j < n; j++)
        {
            rightArraySum += arr[j];
        }
 
        // Multiplying left and right subarray sum
        int k = leftArraySum * rightArraySum;
 
        // Checking for the maximum product
        // of sum of left and right subarray
        if (k > maxProduct)
        {
            maxProduct = k;
        }
    }
 
    // Printing the maximum product
    return maxProduct;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 4, 10, 1, 7, 2, 9 };
    int n = arr.length;
 
    System.out.print(maxProdSum(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
 
# Function to return the maximum
# product of sum for any partition
def maxProdSum(arr, n):
    leftArraySum = 0;
    maxProduct = 0;
 
    # Traversing the array
    for i in range(n):
 
        # Compute left array sum
        leftArraySum += arr[i];
 
        # Compute right array sum
        rightArraySum = 0;
        for j in range(i + 1, n):
            rightArraySum += arr[j];
         
        # Multiplying left and right subarray sum
        k = leftArraySum * rightArraySum;
 
        # Checking for the maximum product
        # of sum of left and right subarray
        if (k > maxProduct):
            maxProduct = k;
         
    # Printing the maximum product
    return maxProduct;
 
# Driver code
if __name__ == '__main__':
    arr = [ 4, 10, 1, 7, 2, 9 ];
    n = len(arr);
 
    print(maxProdSum(arr, n));
 
# This code is contributed by Rajput-Ji

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the maximum
// product of sum for any partition
static int maxProdSum(int []arr, int n)
{
    int leftArraySum = 0, maxProduct = 0;
 
    // Traversing the array
    for (int i = 0; i < n; i++)
    {
 
        // Compute left array sum
        leftArraySum += arr[i];
 
        // Compute right array sum
        int rightArraySum = 0;
        for (int j = i + 1; j < n; j++)
        {
            rightArraySum += arr[j];
        }
 
        // Multiplying left and right subarray sum
        int k = leftArraySum * rightArraySum;
 
        // Checking for the maximum product
        // of sum of left and right subarray
        if (k > maxProduct)
        {
            maxProduct = k;
        }
    }
 
    // Printing the maximum product
    return maxProduct;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 4, 10, 1, 7, 2, 9 };
    int n = arr.Length;
 
    Console.Write(maxProdSum(arr, n));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript implementation of the approach
 
// Function to return the maximum
// product of sum for any partition
function maxProdSum(arr, n) {
    let leftArraySum = 0, maxProduct = 0;
 
    // Traversing the array
    for (let i = 0; i < n; i++) {
 
        // Compute left array sum
        leftArraySum += arr[i];
 
        // Compute right array sum
        let rightArraySum = 0;
        for (let j = i + 1; j < n; j++) {
            rightArraySum += arr[j];
        }
 
        // Multiplying left and right subarray sum
        let k = leftArraySum * rightArraySum;
 
        // Checking for the maximum product
        // of sum of left and right subarray
        if (k > maxProduct) {
            maxProduct = k;
        }
    }
 
    // Printing the maximum product
    return maxProduct;
}
 
// Driver code
 
let arr = [4, 10, 1, 7, 2, 9];
let n = arr.length;
 
document.write(maxProdSum(arr, n));
</script>
Producción: 

270

 

Complejidad temporal: O(N 2 )

Espacio Auxiliar: O(1)

Enfoque eficiente: un mejor enfoque es usar el concepto de suma de array de prefijos que ayuda a calcular la suma de ambas subarreglas contiguas.  

  • El prefijo suma de los elementos se puede calcular.
  • La suma de la array izquierda es el valor en la i -ésima posición.
  • La suma de la array de la derecha es el valor en la última posición: i -ésima posición.
  • Ahora calcule k , el producto de algunos de estos subarreglos izquierdo y derecho.
  • Encuentre e imprima el máximo del producto de estas arrays.

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

CPP

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum
// product of sum for any partition
int maxProdSum(int arr[], int n)
{
    int prefixArraySum[n], maxProduct = 0;
 
    // Initialise prefixArraySum[0]
    // with arr[0] element
    prefixArraySum[0] = arr[0];
 
    // Traverse array elements
    // to compute prefix array sum
    for (int i = 1; i < n; i++) {
        prefixArraySum[i] = prefixArraySum[i - 1]
                            + arr[i];
    }
 
    for (int i = 0; i < n - 1; i++) {
        // Compute left and right array sum
        int leftArraySum = prefixArraySum[i];
        int rightArraySum = prefixArraySum[n - 1]
                            - prefixArraySum[i];
 
        // Multiplying left and right subarray sum
        int k = leftArraySum * rightArraySum;
 
        // Checking for maximum product of
        // the sum of left and right subarray
        if (k > maxProduct) {
            maxProduct = k;
        }
    }
 
    // Printing the maximum value
    return maxProduct;
}
 
// Driver code
int main()
{
    int arr[] = { 4, 10, 1, 7, 2, 9 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << maxProdSum(arr, n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
// Function to return the maximum
// product of sum for any partition
static int maxProdSum(int arr[], int n)
{
    int []prefixArraySum = new int[n];
    int maxProduct = 0;
 
    // Initialise prefixArraySum[0]
    // with arr[0] element
    prefixArraySum[0] = arr[0];
 
    // Traverse array elements
    // to compute prefix array sum
    for (int i = 1; i < n; i++)
    {
        prefixArraySum[i] = prefixArraySum[i - 1]
                            + arr[i];
    }
 
    for (int i = 0; i < n - 1; i++)
    {
        // Compute left and right array sum
        int leftArraySum = prefixArraySum[i];
        int rightArraySum = prefixArraySum[n - 1]
                            - prefixArraySum[i];
 
        // Multiplying left and right subarray sum
        int k = leftArraySum * rightArraySum;
 
        // Checking for maximum product of
        // the sum of left and right subarray
        if (k > maxProduct)
        {
            maxProduct = k;
        }
    }
 
    // Printing the maximum value
    return maxProduct;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 4, 10, 1, 7, 2, 9 };
    int n = arr.length;
 
    System.out.print(maxProdSum(arr, n));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python implementation of the approach
 
# Function to return the maximum
# product of sum for any partition
def maxProdSum(arr, n):
     
    prefixArraySum = [0] * n
    maxProduct = 0
     
    # Initialise prefixArraySum[0]
    # with arr[0] element
    prefixArraySum[0] = arr[0]
     
    # Traverse array elements
    # to compute prefix array sum
    for i in range(1, n):
        prefixArraySum[i] = prefixArraySum[i - 1] + arr[i]
     
    for i in range(n - 1):
         
        # Compute left and right array sum
        leftArraySum = prefixArraySum[i]
        rightArraySum = prefixArraySum[n - 1] - \
                        prefixArraySum[i]
         
        # Multiplying left and right subarray sum
        k = leftArraySum * rightArraySum
         
        # Checking for maximum product of
        # the sum of left and right subarray
        if (k > maxProduct):
            maxProduct = k
     
    # Printing the maximum value
    return maxProduct
 
# Driver code
arr = [4, 10, 1, 7, 2, 9]
n = len(arr)
print(maxProdSum(arr, n))
 
# This code is contributed by SHUBHAMSINGH10

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the maximum
// product of sum for any partition
static int maxProdSum(int []arr, int n)
{
    int []prefixArraySum = new int[n];
    int maxProduct = 0;
 
    // Initialise prefixArraySum[0]
    // with arr[0] element
    prefixArraySum[0] = arr[0];
 
    // Traverse array elements
    // to compute prefix array sum
    for (int i = 1; i < n; i++)
    {
        prefixArraySum[i] = prefixArraySum[i - 1]
                            + arr[i];
    }
 
    for (int i = 0; i < n - 1; i++)
    {
        // Compute left and right array sum
        int leftArraySum = prefixArraySum[i];
        int rightArraySum = prefixArraySum[n - 1]
                            - prefixArraySum[i];
 
        // Multiplying left and right subarray sum
        int k = leftArraySum * rightArraySum;
 
        // Checking for maximum product of
        // the sum of left and right subarray
        if (k > maxProduct)
        {
            maxProduct = k;
        }
    }
 
    // Printing the maximum value
    return maxProduct;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 4, 10, 1, 7, 2, 9 };
    int n = arr.Length;
 
    Console.Write(maxProdSum(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript implementation of the approach
 
// Function to return the maximum
// product of sum for any partition
function maxProdSum(arr, n)
{
    let prefixArraySum = [], maxProduct = 0;
 
    // Initialise prefixArraySum[0]
    // with arr[0] element
    prefixArraySum[0] = arr[0];
 
    // Traverse array elements
    // to compute prefix array sum
    for (let i = 1; i < n; i++) {
        prefixArraySum[i] = prefixArraySum[i - 1]
                            + arr[i];
    }
 
    for (let i = 0; i < n - 1; i++) {
        // Compute left and right array sum
        let leftArraySum = prefixArraySum[i];
        let rightArraySum = prefixArraySum[n - 1]
                            - prefixArraySum[i];
 
        // Multiplying left and right subarray sum
        let k = leftArraySum * rightArraySum;
 
        // Checking for maximum product of
        // the sum of left and right subarray
        if (k > maxProduct) {
            maxProduct = k;
        }
    }
 
    // Printing the maximum value
    return maxProduct;
}
 
// Driver code
let arr = [ 4, 10, 1, 7, 2, 9 ];
let n = arr.length;
 
document.write(maxProdSum(arr, n));
 
// This code is contributed by Samim Hossain Mondal.
</script>
Producción: 

270

 

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por Chauhanvishesh99 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 *