Dada una array arr[] , la tarea es encontrar la suma de los elementos mínimos de cada subarreglo posible de la array.
Ejemplos:
Entrada: array[] = {1, 3, 2}
Salida: 15
Todas las sub-arrays posibles son {1}, {2}, {3}, {1, 3}, {3, 2} y {1, 3 , 2}
Y, la suma de todos los elementos mínimos es 1 + 2 + 3 + 1 + 2 + 1 = 10
Entrada: arr[] = {3, 1}
Salida: 5
Un método simple es generar todos los sub-arreglos y luego sumar los elementos mínimos en todos ellos. La complejidad temporal de esta solución será O(n 3 ).
Mejor método:
la clave para la optimización es la pregunta :
¿En cuántos segmentos el valor de un índice será mínimo?
La siguiente idea que nos puede venir a la mente será para cada índice i en el arreglo arr , tratamos de encontrar:
Recuento izquierdo: Iteramos hacia la izquierda del índice i hasta que no encontremos un elemento estrictamente menor que arr[ i] o no llegamos al extremo izquierdo de la array. Llamemos a esta cuenta para el índice i de la array dada como CLi .
Recuento correcto: Iteramos hacia la derecha del índice hasta que no encontremos un elemento menor o igual que el valor del índice, o no alcancemos el extremo derecho. Llamemos a esta cuenta para el índice ide la array dada como CRi .
(CLi + 1) * (CRi + 1) será el número de subarreglos para el índice i actual en el que su valor será mínimo porque hay CLi + 1 formas de elegir elementos del lado izquierdo (incluida la elección de ningún elemento ) y CRi + 1 formas de elegir elementos del lado derecho.
La complejidad temporal de este enfoque será O(n 2 )
El mejor método:
este problema se puede resolver utilizando una estructura de datos de pila en tiempo O (n) . La idea sigue siendo la misma que en el enfoque anterior. Para ahorrar algo de tiempo, usaremos una pila de la biblioteca de plantillas estándar de C++.
Conteo izquierdo: Deje que CLi represente el conteo izquierdo para un índice i . CLi para un índice i se puede definir como el número de elementos entre el índice i y el elemento más a la derecha cuyo valor es estrictamente menor que arr[i] que tiene un índice menor que i . Si no existe tal elemento, entonces CLipara un elemento será igual al número de elementos a la izquierda del índice i .
Para lograr esto, insertaremos solo el índice de los elementos de izquierda a derecha en la pila. Supongamos que estamos insertando un índice i en la pila y j sea el índice del elemento superior actualmente presente en la pila. Si bien el valor arr[i] es menor o igual que el valor en el índice superior de la pila y la pila no está vacía, siga extrayendo los elementos de la pila. Cada vez que se extrae un elemento, el conteo izquierdo (CLi) del índice actual (i) se actualiza como CLi = CLi + CLj + 1 .
Cuenta correcta:Calculamos el conteo correcto para todos los índices de manera similar. La única diferencia es que empujamos los elementos en la pila mientras los desplazamos de derecha a izquierda en la array. Si bien arr[i] es estrictamente menor que el valor en el índice superior de la pila y la pila no está vacía, siga extrayendo los elementos. Cada vez que se extrae un elemento, el recuento correcto del índice actual (i) se actualiza como CRi = CRi + CRj + 1 .
Paso final: Sea ans la variable que contiene la respuesta final. Lo inicializaremos con 0 . Luego, iteraremos a través de todos los índices del 1 al n de la array y actualizaremos el ans comoans = ans + (CLi + 1) * (CRi + 1) * arr[i] para todos los valores posibles de i de 1 a n .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
#include <stack>
using namespace std;
// Function to return the required sum
int findMinSum(int arr[], int n)
{
// Arrays for maintaining left and right count
int CL[n] = { 0 }, CR[n] = { 0 };
// Stack for storing the indexes
stack<int> q;
// Calculate left count for every index
for (int i = 0; i < n; i++) {
while (q.size() != 0 && arr[q.top()] >= arr[i]) {
CL[i] += CL[q.top()] + 1;
q.pop();
}
q.push(i);
}
// Clear the stack
while (q.size() != 0)
q.pop();
// Calculate right count for every index
for (int i = n - 1; i >= 0; i--) {
while (q.size() != 0 && arr[q.top()] > arr[i]) {
CR[i] += CR[q.top()] + 1;
q.pop();
}
q.push(i);
}
// Clear the stack
while (q.size() != 0)
q.pop();
// To store the required sum
int ans = 0;
// Calculate the final sum
for (int i = 0; i < n; i++)
ans += (CL[i] + 1) * (CR[i] + 1) * arr[i];
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMinSum(arr, n);
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to return the required sum
static int findMinSum(int arr[], int n)
{
// Arrays for maintaining left and right count
int CL[] = new int[n], CR[] = new int[n];
// Stack for storing the indexes
Stack<Integer> q = new Stack<Integer>();
// Calculate left count for every index
for (int i = 0; i < n; i++)
{
while (q.size() != 0 && arr[q.peek()] >= arr[i])
{
CL[i] += CL[q.peek()] + 1;
q.pop();
}
q.push(i);
}
// Clear the stack
while (q.size() != 0)
q.pop();
// Calculate right count for every index
for (int i = n - 1; i >= 0; i--)
{
while (q.size() != 0 && arr[q.peek()] > arr[i])
{
CR[i] += CR[q.peek()] + 1;
q.pop();
}
q.push(i);
}
// Clear the stack
while (q.size() != 0)
q.pop();
// To store the required sum
int ans = 0;
// Calculate the final sum
for (int i = 0; i < n; i++)
ans += (CL[i] + 1) * (CR[i] + 1) * arr[i];
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 2 };
int n = arr.length;
System.out.println(findMinSum(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the required sum def findMinSum(arr, n): # Arrays for maintaining left and # right count CL = [0] * n CR = [0] * n # Stack for storing the indexes q = [] # Calculate left count for every index for i in range(0, n): while (len(q) != 0 and arr[q[-1]] >= arr[i]): CL[i] += CL[q[-1]] + 1 q.pop() q.append(i) # Clear the stack while len(q) != 0: q.pop() # Calculate right count for every index for i in range(n - 1, -1, -1): while (len(q) != 0 and arr[q[-1]] > arr[i]): CR[i] += CR[q[-1]] + 1 q.pop() q.append(i) # Clear the stack while len(q) != 0: q.pop() # To store the required sum ans = 0 # Calculate the final sum for i in range(0, n): ans += (CL[i] + 1) * (CR[i] + 1) * arr[i] return ans # Driver code if __name__ == "__main__": arr = [1, 3, 2] n = len(arr) print(findMinSum(arr, n)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the required sum
static int findMinSum(int []arr, int n)
{
// Arrays for maintaining left and right count
int []CL = new int[n];
int []CR = new int[n];
// Stack for storing the indexes
Stack<int> q = new Stack<int>();
// Calculate left count for every index
for (int i = 0; i < n; i++)
{
while (q.Count != 0 && arr[q.Peek()] >= arr[i])
{
CL[i] += CL[q.Peek()] + 1;
q.Pop();
}
q.Push(i);
}
// Clear the stack
while (q.Count != 0)
q.Pop();
// Calculate right count for every index
for (int i = n - 1; i >= 0; i--)
{
while (q.Count != 0 && arr[q.Peek()] > arr[i])
{
CR[i] += CR[q.Peek()] + 1;
q.Pop();
}
q.Push(i);
}
// Clear the stack
while (q.Count != 0)
q.Pop();
// To store the required sum
int ans = 0;
// Calculate the final sum
for (int i = 0; i < n; i++)
ans += (CL[i] + 1) * (CR[i] + 1) * arr[i];
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 3, 2 };
int n = arr.Length;
Console.WriteLine(findMinSum(arr, n));
}
}
// This code has been contributed
// by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to return the required sum
function findMinSum(arr, n)
{
// Arrays for maintaining left and right count
var CL = Array(n).fill(0);
var CR = Array(n).fill(0);
// Stack for storing the indexes
var q = [];
// Calculate left count for every index
for (var i = 0; i < n; i++) {
while (q.length != 0 && arr[q[q.length-1]] >= arr[i]) {
CL[i] += CL[q[q.length-1]] + 1;
q.pop();
}
q.push(i);
}
// Clear the stack
while((q.length) != 0)
q.pop();
// Calculate right count for every index
for (var i = n - 1; i >= 0; i--) {
while (q.length != 0 && arr[q[q.length-1]] > arr[i]) {
CR[i] += CR[q[q.length-1]] + 1;
q.pop();
}
q.push(i);
}
// Clear the stack
while((q.length) != 0)
q.pop();
// To store the required sum
var ans = 0;
// Calculate the final sum
for (var i = 0; i < n; i++)
ans += (CL[i] + 1) * (CR[i] + 1) * arr[i];
return ans;
}
// Driver code
var arr = [1, 3, 2 ];
var n = arr.length;
document.write( findMinSum(arr, n));
</script>
10
Complejidad temporal: O(n)
Espacio auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA