Dado un arreglo arr[] de N enteros positivos, la tarea es encontrar la suma del producto de los elementos de todos los subarreglos posibles.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 20
Explicación: Los posibles subarreglos son: {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2 , 3}.
Los productos de todos los subarreglos anteriores son 1, 2, 3, 2, 6 y 6 respectivamente.
Suma de todos los productos = 1 + 2 + 3 + 2 + 6 + 6 = 20.Entrada: arr[] = {1, 2, 3, 4}
Salida: 84
Explicación:
Los posibles subarreglos son: {1}, {2}, {3}, {4}, {1, 2}, {2, 3 }, {3, 4}, {1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}. Los productos de todos los subarreglos anteriores son 1, 2, 3, 4, 2, 6, 12, 6, 24 y 24.
Suma de todos los productos = 1 + 2 + 3 + 4 + 2 + 6 + 12 + 6 + 24 + 24 = 84.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y calcular el producto de todos los elementos de cada subarreglo y sumarlo a la suma final.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar el problema en algún patrón. Supongamos que tenemos cuatro números a , b , c y d . Podemos escribir todos los posibles productos de subarreglos como:
a + b + c + ab + bc + cd + abc + bcd + abcd
= (a + ab + abc + abcd) + (b + bc + bcd) + (c + cd) + d
= a * (1+ b + ac + bcd ) + (b + ac + bcd) + (c + cd) + reAhora, el valor de la expresión subrayada (b + bc + bcd) se puede calcular una vez y usar dos veces.
De nuevo, (b+ bc + bcd) + (c + cd) = b * (1 + c + cd ) + ( c + cd )De la misma manera, la expresión (c + cd) se puede usar dos veces.
La última parte es la misma que la anterior.
Siga los pasos a continuación para resolver el problema:
- Repita el último elemento y actualice la expresión recurrente con cada elemento y utilícela más. En este proceso, actualice el resultado en consecuencia.
- Inicialice ans como 0 que almacenará la suma final y res como 0 que mantendrá la pista del valor del producto de todos los elementos del subarreglo anterior.
- Recorra la array desde atrás y para cada elemento, arr[i] haga lo siguiente:
- Incremente ans por el producto de arr[i] y (1 + res) .
- Actualice res a arr[i]*(1 + res) .
- Después de los pasos anteriores, imprima la suma del producto de todos los subarreglos almacenados en ans .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that finds the sum of
// products of all subarray of arr[]
void sumOfSubarrayProd(int arr[], int n)
{
// Stores sum of all subarrays
int ans = 0;
int res = 0;
// Iterate array from behind
for(int i = n - 1; i >= 0; i--)
{
int incr = arr[i] * (1 + res);
// Update the ans
ans += incr;
// Update the res
res = incr;
}
// Print the final sum
cout << (ans);
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 3 };
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
sumOfSubarrayProd(arr, N);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function that finds the sum of
// products of all subarray of arr[]
static void sumOfSubarrayProd(int arr[],
int n)
{
// Stores sum of all subarrays
int ans = 0;
int res = 0;
// Iterate array from behind
for (int i = n - 1; i >= 0; i--) {
int incr = arr[i] * (1 + res);
// Update the ans
ans += incr;
// Update the res
res = incr;
}
// Print the final sum
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 3 };
// Size of array
int N = arr.length;
// Function Call
sumOfSubarrayProd(arr, N);
}
}
Python3
# Python3 program for the above approach # Function that finds the sum of # products of all subarray of arr[] def sumOfSubarrayProd(arr, n): # Stores sum of all subarrays ans = 0 res = 0 # Iterate array from behind i = n - 1 while(i >= 0): incr = arr[i] * (1 + res) # Update the ans ans += incr # Update the res res = incr i -= 1 # Print the final sum print(ans) # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 1, 2, 3 ] # Size of array N = len(arr) # Function call sumOfSubarrayProd(arr, N) # This code is contributed by ipg2016107
C#
// C# program for the
// above approach
using System;
// Function that finds
// the sum of products
// of all subarray of arr[]
class solution{
static void sumOfSubarrayProd(int []arr,
int n)
{
// Stores sum of all
// subarrays
int ans = 0;
int res = 0;
// Iterate array from behind
for(int i = n - 1; i >= 0; i--)
{
int incr = arr[i] * (1 + res);
// Update the ans
ans += incr;
// Update the res
res = incr;
}
// Print the final sum
Console.WriteLine(ans);
}
// Driver Code
public static void Main(String[] args)
{
// Given array arr[]
int []arr = {1, 2, 3 };
// Size of array
int N = arr.Length;
// Function call
sumOfSubarrayProd(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program to implement
// the above approach
// Function that finds the sum of
// products of all subarray of arr[]
function sumOfSubarrayProd(arr, n)
{
// Stores sum of all subarrays
let ans = 0;
let res = 0;
// Iterate array from behind
for (let i = n - 1; i >= 0; i--) {
let incr = arr[i] * (1 + res);
// Update the ans
ans += incr;
// Update the res
res = incr;
}
// Print the final sum
document.write(ans);
}
// Driver Code
// Given array arr[]
let arr = [ 1, 2, 3 ];
// Size of array
let N = arr.length;
// Function Call
sumOfSubarrayProd(arr, N);
</script>
20
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array