Dada una array A de n enteros. La tarea es encontrar la suma del mínimo de todos los subarreglos posibles (contiguos) de A .
Ejemplos:
Entrada: A = [3, 1, 2, 4]
Salida: 17
Explicación: Los subarreglos son [3], [1], [2], [4], [3, 1], [1, 2], [2 , 4], [3, 1, 2], [1, 2, 4], [3, 1, 2, 4].
Los mínimos son 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. La suma es 17.
Entrada: A = [1, 2, 3, 4]
Salida: 20
Enfoque: el enfoque Naive es generar todos los subarreglos posibles (contiguos), encontrar su mínimo y agregarlos al resultado. La complejidad temporal será O(N 2 ).
Enfoque eficiente: la intuición general para la solución del problema es encontrar sum(A[i] * f(i)) , donde f(i) es el número de subarreglos en los que A[i] es el mínimo.
Para encontrar f[i] , necesitamos encontrar:
left[i] , la longitud de los números estrictamente más grandes a la izquierda de A[i] ,
right[i] , la longitud de los números más grandes a la derecha de A [yo] .
Hacemos dos arreglos left[ ] y right[ ] tales que:
left[i] + 1 es igual al número de subarreglos que terminan en A[i] , y A[i] es solo un mínimo.
De manera similar, right[i] + 1 es igual al número de subarreglos que comienzan con A[i] , y A[i] es el primer mínimo.
Finalmente, f(i) = (left[i]) * (right[i]) , donde f[i] es igual al número total de subarreglos en los que A[i] es mínimo.x
A continuación se muestra la implementación del enfoque anterior
C++
// CPP implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return required minimum sum
int sumSubarrayMins(int A[], int n)
{
int left[n], right[n];
stack<pair<int, int> > s1, s2;
// getting number of element strictly larger
// than A[i] on Left.
for (int i = 0; i < n; ++i) {
int cnt = 1;
// get elements from stack until element
// greater than A[i] found
while (!s1.empty() && (s1.top().first) > A[i]) {
cnt += s1.top().second;
s1.pop();
}
s1.push({ A[i], cnt });
left[i] = cnt;
}
// getting number of element larger than A[i] on Right.
for (int i = n - 1; i >= 0; --i) {
int cnt = 1;
// get elements from stack until element greater
// or equal to A[i] found
while (!s2.empty() && (s2.top().first) >= A[i]) {
cnt += s2.top().second;
s2.pop();
}
s2.push({ A[i], cnt });
right[i] = cnt;
}
int result = 0;
// calculating required resultult
for (int i = 0; i < n; ++i)
result = (result + A[i] * left[i] * right[i]);
return result;
}
// Driver program
int main()
{
int A[] = { 3, 1, 2, 4 };
int n = sizeof(A) / sizeof(A[0]);
// function call to get required resultult
cout << sumSubarrayMins(A, n);
return 0;
}
// This code is written by Sanjit_Prasad
Java
// Java implementation of above approach
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to return required minimum sum
static int sumSubarrayMins(int A[], int n)
{
int []left = new int[n];
int []right = new int[n];
Stack<pair> s1 = new Stack<pair>();
Stack<pair> s2 = new Stack<pair>();
// getting number of element strictly larger
// than A[i] on Left.
for (int i = 0; i < n; ++i)
{
int cnt = 1;
// get elements from stack until element
// greater than A[i] found
while (!s1.isEmpty() &&
(s1.peek().first) > A[i])
{
cnt += s1.peek().second;
s1.pop();
}
s1.push(new pair(A[i], cnt));
left[i] = cnt;
}
// getting number of element larger
// than A[i] on Right.
for (int i = n - 1; i >= 0; --i)
{
int cnt = 1;
// get elements from stack until element
// greater or equal to A[i] found
while (!s2.isEmpty() &&
(s2.peek().first) >= A[i])
{
cnt += s2.peek().second;
s2.pop();
}
s2.push(new pair(A[i], cnt));
right[i] = cnt;
}
int result = 0;
// calculating required resultult
for (int i = 0; i < n; ++i)
result = (result + A[i] * left[i] *
right[i]);
return result;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 3, 1, 2, 4 };
int n = A.length;
// function call to get required result
System.out.println(sumSubarrayMins(A, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of above approach # Function to return required minimum sum def sumSubarrayMins(A, n): left, right = [None] * n, [None] * n # Use list as stack s1, s2 = [], [] # getting number of element strictly # larger than A[i] on Left. for i in range(0, n): cnt = 1 # get elements from stack until # element greater than A[i] found while len(s1) > 0 and s1[-1][0] > A[i]: cnt += s1[-1][1] s1.pop() s1.append([A[i], cnt]) left[i] = cnt # getting number of element # larger than A[i] on Right. for i in range(n - 1, -1, -1): cnt = 1 # get elements from stack until # element greater or equal to A[i] found while len(s2) > 0 and s2[-1][0] >= A[i]: cnt += s2[-1][1] s2.pop() s2.append([A[i], cnt]) right[i] = cnt result = 0 # calculating required resultult for i in range(0, n): result += A[i] * left[i] * right[i] return result # Driver Code if __name__ == "__main__": A = [3, 1, 2, 4] n = len(A) # function call to get # required resultult print(sumSubarrayMins(A, n)) # This code is contributed # by Rituraj Jain
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to return required minimum sum
static int sumSubarrayMins(int []A, int n)
{
int []left = new int[n];
int []right = new int[n];
Stack<pair> s1 = new Stack<pair>();
Stack<pair> s2 = new Stack<pair>();
// getting number of element strictly larger
// than A[i] on Left.
for (int i = 0; i < n; ++i)
{
int cnt = 1;
// get elements from stack until element
// greater than A[i] found
while (s1.Count!=0 &&
(s1.Peek().first) > A[i])
{
cnt += s1.Peek().second;
s1.Pop();
}
s1.Push(new pair(A[i], cnt));
left[i] = cnt;
}
// getting number of element larger
// than A[i] on Right.
for (int i = n - 1; i >= 0; --i)
{
int cnt = 1;
// get elements from stack until element
// greater or equal to A[i] found
while (s2.Count != 0 &&
(s2.Peek().first) >= A[i])
{
cnt += s2.Peek().second;
s2.Pop();
}
s2.Push(new pair(A[i], cnt));
right[i] = cnt;
}
int result = 0;
// calculating required resultult
for (int i = 0; i < n; ++i)
result = (result + A[i] * left[i] *
right[i]);
return result;
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 3, 1, 2, 4 };
int n = A.Length;
// function call to get required result
Console.WriteLine(sumSubarrayMins(A, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of above approach
// Function to return required minimum sum
function sumSubarrayMins(A, n)
{
var left = Array(n), right = Array(n);
var s1 = [], s2 = [];
// getting number of element strictly larger
// than A[i] on Left.
for (var i = 0; i < n; ++i) {
var cnt = 1;
// get elements from stack until element
// greater than A[i] found
while (s1.length!=0 && (s1[s1.length-1][0]) > A[i]) {
cnt += s1[s1.length-1][1];
s1.pop();
}
s1.push([A[i], cnt]);
left[i] = cnt;
}
// getting number of element larger than A[i] on Right.
for (var i = n - 1; i >= 0; --i) {
var cnt = 1;
// get elements from stack until element greater
// or equal to A[i] found
while (s2.length!=0 && (s2[s2.length-1][0]) >= A[i]) {
cnt += s2[s2.length-1][1];
s2.pop();
}
s2.push([A[i], cnt]);
right[i] = cnt;
}
var result = 0;
// calculating required resultult
for (var i = 0; i < n; ++i)
result = (result + A[i] * left[i] * right[i]);
return result;
}
// Driver program
var A = [3, 1, 2, 4];
var n = A.length;
// function call to get required resultult
document.write( sumSubarrayMins(A, n));
</script>
Producción
17
Complejidad Temporal: O(N), donde N es la longitud de A.
Complejidad Espacial: O(N).
Otro enfoque :
Es un enfoque de programación dinámica .
Primero, calcule el siguiente índice de elemento más pequeño en el lado derecho para cada índice usando pilas.
En cualquier índice i, dp[i] denota la suma total de todos los subconjuntos a partir del índice i.
Para calcular la respuesta de cada índice, habrá dos casos:
- El elemento actual es el elemento más pequeño entre todos los elementos del lado derecho. Entonces ans será (( range of curr_index * arr[curr_index] )) . Como será el elemento más pequeño en todos los subconjuntos a partir de curr_index.
- Hay un elemento presente a la derecha, que es más pequeño que el elemento actual. La respuesta de ese elemento más pequeño ya está almacenada en dp. Simplemente calcule la respuesta desde el índice_actual hasta el índice_derecho_más_pequeño.
- upto_smaller = (right_index – curr_index)*arr[curr_index] ## suma a la forma de índice más pequeño de la derecha curr_index .
- curr_sum = upto_smaller + dp[right_index]
Finalmente, devuelva la suma (dp).
Por ejemplo: – arr = [4,3,6]
pd[6] = 6
dp[3] => (3-1)*3 => 6 #elemento más pequeño
pd[4] = (1 -0) *(4) + pd[3] => 4 + 6 => 10
Respuesta final = 6 + 6 + 10= 22
C++
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
int sumSubarrayMins(int arr[], int n)
{
int dp[n];
for (int i = 0; i < n; i++)
dp[i] = 0;
// calculate right smaller element
int right[n];
for (int i = 0; i < n; i++) {
right[i] = i;
}
vector<int> stack{ 0 };
for (int i = 1; i < n; i++) {
int curr = arr[i];
while ((stack.size() > 0)
&& (curr < arr[stack.back()])) {
int idx = stack.back();
stack.pop_back();
right[idx] = i;
}
stack.push_back(i);
}
dp[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
int right_idx = right[i];
if (right_idx == i) { // case 1
int curr = (n - i) * arr[i];
dp[i] = curr;
}
else { // case 2
// sum upto next smaller rhs element
int upto_small = (right_idx - i) * (arr[i]);
int curr_sum = (upto_small + dp[right_idx]);
dp[i] = curr_sum;
}
}
//calculating sum of dp
int sum = 0;
sum = accumulate(dp, dp + n, sum);
return sum;
}
// Driver Code
int main()
{
int A[] = { 3, 1, 2, 4 };
int n = sizeof(A) / sizeof(A[0]);
// function call to get
// required result
cout << sumSubarrayMins(A, n) << endl;
}
// This code is contributed by phasing17
Java
// Java program to implement the approach
import java.util.*;
public class GFG {
static int sumSubarrayMins(int[] arr, int n)
{
int dp[] = new int[n];
for (int i = 0; i < n; i++)
dp[i] = 0;
// calculate right smaller element
int right[] = new int[n];
for (int i = 0; i < n; i++) {
right[i] = i;
}
ArrayList<Integer> stack = new ArrayList<Integer>();
stack.add(0);
for (int i = 1; i < n; i++) {
int curr = arr[i];
while (
(stack.size() > 0)
&& (curr
< arr[stack.get(stack.size() - 1)])) {
int idx = stack.get(stack.size() - 1);
stack.remove(stack.size() - 1);
right[idx] = i;
}
stack.add(i);
}
dp[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
int right_idx = right[i];
if (right_idx == i) { // case 1
int curr = (n - i) * arr[i];
dp[i] = curr;
}
else { // case 2
// sum upto next smaller rhs element
int upto_small = (right_idx - i) * (arr[i]);
int curr_sum = (upto_small + dp[right_idx]);
dp[i] = curr_sum;
}
}
// calculating sum of dp
int sum = 0;
for (int i = 0; i < dp.length; i++)
sum += dp[i];
return sum;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 3, 1, 2, 4 };
int n = A.length;
// function call to get
// required result
System.out.println(sumSubarrayMins(A, n));
}
}
// This code is contributed by phasing17
Python3
def sumSubarrayMins(arr, n): dp = [0]*(n) # calculate right smaller element right = [i for i in range(n)] stack = [0] for i in range(1,n,1): curr = arr[i] while(stack and curr < arr[stack[-1]]): idx = stack.pop() right[idx] = i stack.append(i) dp[-1] = arr[-1] for i in range(n-2,-1,-1): right_idx = right[i] if right_idx == i: # case 1 curr = (n-i)*arr[i] dp[i] = curr else: # case 2 # sum upto next smaller rhs element upto_small = (right_idx-i)*(arr[i]) curr_sum = (upto_small + dp[right_idx]) dp[i] = curr_sum return (sum(dp)) # Driver Code if __name__ == "__main__": A = [3, 1, 2, 4] n = len(A) # function call to get # required resultult print(sumSubarrayMins(A, n))
Javascript
<script>
function sumSubarrayMins(arr, n)
{
let dp = new Array(n).fill(0)
// calculate right smaller element
let right = new Array(n);
for(let i = 0; i < n; i++)
{
right[i] = i;
}
let stack = [0]
for(let i = 1; i < n; i++){
let curr = arr[i]
while(stack && curr < arr[stack[stack.length-1]]){
let idx = stack.shift()
right[idx] = i
}
stack.push(i)
}
dp[dp.length - 1] = arr[arr.length - 1]
for(let i = n - 2; i >= 0; i--){
let right_idx = right[i]
if(right_idx == i){ // case 1
let curr = (n - i)*arr[i]
dp[i] = curr
}
else{ // case 2
// sum upto next smaller rhs element
let upto_small = (right_idx-i)*(arr[i])
let curr_sum = (upto_small + dp[right_idx])
dp[i] = curr_sum
}
}
let sum = 0
for(let i of dp){
sum += i
}
return sum
}
// Driver Code
let A = [3, 1, 2, 4]
let n = A.length
// function call to get
// required resultult
document.write(sumSubarrayMins(A, n))
// This code is contributed by shinjanpatra
</script>
Producción
17
Complejidad de tiempo y espacio := O(N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA