Dada una array arr[] , la tarea es encontrar la suma de los elementos máximos de cada sub-array 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áximos es 1 + 2 + 3 + 3 + 3 + 3 = 15
Entrada: arr[] = {3, 1}
Salida: 7
Un método simple es generar todos los sub-arreglos y luego sumar los elementos máximos en todos ellos. La complejidad temporal de esta solución será O(n 3 ).
Un método mejor:
la clave para la optimización es la pregunta :
¿En cuántos segmentos el valor de un índice será máximo?
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 mayor 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 derecho: Iteramos hacia la derecha del índice hasta que no encontramos un elemento mayor o igual que el valor del índice, o no llegamos al 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áximo 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 )
Más Mejor método:
La idea es ordenar la array dada. Así que el primer elemento vendrá por una vez, el segundo elemento vendrá por dos veces, y así sucesivamente. Entonces, la suma total será la suma de (i+1)*(array_ordenada[i]).
La complejidad temporal de este enfoque será O(nlog(n))
Mejor método:
este problema se puede resolver utilizando la estructura de datos de la pila en tiempo O (n) . La idea sigue siendo la misma que en el enfoque anterior. Para ahorrar algo de tiempo, usaremos la 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 mayor 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 mayor 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 mayor 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 findMaxSum(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 << findMaxSum(arr, n);
}
Java
// Java implementation of the above approach
import java.util.*;
public class GFG
{
// Function to return the required sum
static int findMaxSum(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(findMaxSum(arr, n));
}
}
// This code is contributed by Rituraj Jain
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 findMaxSum(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(findMaxSum(arr, n));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to return the required sum
function findMaxSum(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( findMaxSum(arr, n));
</script>
15
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