Dado un arreglo arr[] , la tarea es encontrar la suma del valor de descomposición del sufijo subarreglo.
Valor de descomposición: El valor de descomposición de un subarreglo es el recuento de la partición en el subarreglo posible. La partición en la array en el índice 
se puede hacer solo si los elementos de la array anterior son menores que el índice actual. Eso es A[k] < A[i], donde k ≤ i.
Ejemplos:
Entrada: arr[] = {2, 8, 4}
Salida: 4
Explicación:
Todos los sufijos del subarreglo de arr[] son [2, 8, 4], [8, 4], [4]
Sufijo [4] => solamente 1 descomposición {4}
Sufijo [8, 4] => solo 1 descomposición {8, 4}
Sufijo [2, 8, 4] => 2 descomposiciones {2, 8, 4}, {2} {8, 4}
Por lo tanto , Suma de valores de descomposición = 1 + 1 + 2 = 4
Entrada: arr[] = {9, 6, 9, 35}
Salida: 8
Explicación:
Todos los sufijos de arr son [9, 6, 9, 35], [6 , 9, 35], [9, 35], [35]
Sufijo [35] => solo 1 descomposición {35}
Sufijo [9, 35] => 2 descomposiciones {9} {35}
Sufijo [6, 9, 35 ] => 3 descomposiciones {6} {9, 35}
Sufijo [9, 6, 9, 35] => 2 descomposiciones {9, 6, 9} {35}
Por lo tanto, la suma de los valores de descomposición = 1 + 2 + 3 + 2 = 8
Enfoque: La idea es usar Stack para resolver este problema. A continuación se muestra la ilustración del enfoque.
- Atraviesa la array desde el final hasta el principio.
- Mantenga una variable mínima y una variable de respuesta.
- Si la pila está vacía o el elemento actual es menor que la parte superior de la pila:
- Empuje S[i] en la pila.
- Incrementa la respuesta por el tamaño de la pila.
- Además, mantenga el valor mínimo hasta ahora.
- De lo contrario,
- Siga haciendo estallar los bloques siempre que la parte superior de la pila sea menor que el elemento actual.
- Actualice el valor mínimo hasta ahora con el elemento actual.
- Empuje el valor mínimo en la pila. Porque queremos que el valor mínimo del subarreglo represente ese subarreglo
- Incrementa la respuesta por el tamaño de la pila.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// sum of Decomposition values of
// all suffixes of an array
#include <bits/stdc++.h>
using namespace std;
#define int long long int
// Function to find the decomposition
// values of the array
int decompose(vector<int> S)
{
// Stack
stack<int> s;
int N = S.size();
int ans = 0;
// Variable to maintain
// min value in stack
int nix = INT_MAX;
// Loop to iterate over the array
for (int i = N - 1; i >= 0; i--) {
// Condition to check if the
// stack is empty
if (s.empty()) {
s.push(S[i]);
nix = S[i];
}
else {
// Condition to check if the
// top of the stack is greater
// than the current element
if (S[i] < s.top()) {
s.push(S[i]);
nix = min(nix, S[i]);
}
else {
int val = S[i];
// Loop to pop the element out
while (!s.empty() &&
val >= s.top()) {
s.pop();
}
nix = min(nix, S[i]);
s.push(nix);
}
}
// the size of the stack is the
// max no of subarrays for
// suffix till index i
// from the right
ans += s.size();
}
return ans;
}
// Driver Code
signed main()
{
vector<int> S = { 9, 6, 9, 35 };
cout << decompose(S) << endl;
return 0;
}
Java
// Java implementation to find the
// sum of Decomposition values of
// all suffixes of an array
import java.util.*;
class GFG{
// Function to find the decomposition
// values of the array
static int decompose(Vector<Integer> S)
{
// Stack
Stack<Integer> s = new Stack<Integer>();
int N = S.size();
int ans = 0;
// Variable to maintain
// min value in stack
int nix = Integer.MAX_VALUE;
// Loop to iterate over the array
for(int i = N - 1; i >= 0; i--)
{
// Condition to check if the
// stack is empty
if (s.isEmpty())
{
s.add(S.get(i));
nix = S.get(i);
}
else
{
// Condition to check if the
// top of the stack is greater
// than the current element
if (S.get(i) < s.peek())
{
s.add(S.get(i));
nix = Math.min(nix, S.get(i));
}
else
{
int val = S.get(i);
// Loop to pop the element out
while (!s.isEmpty() && val >= s.peek())
{
s.pop();
}
nix = Math.min(nix, S.get(i));
s.add(nix);
}
}
// The size of the stack is the
// max no of subarrays for
// suffix till index i
// from the right
ans += s.size();
}
return ans;
}
// Driver Code
public static void main(String args[])
{
Vector<Integer> S = new Vector<Integer>();
S.add(9);
S.add(6);
S.add(9);
S.add(35);
System.out.println(decompose(S));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to find the # sum of Decomposition values of # all suffixes of an array import sys # Function to find the decomposition # values of the array def decompose(S): # Stack s = [] N = len(S) ans = 0 # Variable to maintain # min value in stack nix = sys.maxsize # Loop to iterate over the array for i in range(N - 1, -1, -1): # Condition to check if the # stack is empty if (len(s) == 0): s.append(S[i]) nix = S[i] else: # Condition to check if the # top of the stack is greater # than the current element if (S[i] < s[-1]): s.append(S[i]) nix = min(nix, S[i]) else: val = S[i] # Loop to pop the element out while (len(s) != 0 and val >= s[-1]): s.pop() nix = min(nix, S[i]); s.append(nix) # The size of the stack is the # max no of subarrays for # suffix till index i # from the right ans += len(s) return ans # Driver Code if __name__ =="__main__": S = [ 9, 6, 9, 35 ] print(decompose(S)) # This code is contributed by chitranayal
C#
// C# implementation to find the
// sum of Decomposition values of
// all suffixes of an array
using System;
using System.Collections.Generic;
class GFG{
// Function to find the decomposition
// values of the array
static int decompose(List<int> S)
{
// Stack
Stack<int> s = new Stack<int>();
int N = S.Count;
int ans = 0;
// Variable to maintain
// min value in stack
int nix = Int32.MaxValue;
// Loop to iterate over the array
for(int i = N - 1; i >= 0; i--)
{
// Condition to check if the
// stack is empty
if (s.Count == 0)
{
s.Push(S[i]);
nix = S[i];
}
else
{
// Condition to check if the
// top of the stack is greater
// than the current element
if (S[i] < s.Peek())
{
s.Push(S[i]);
nix = Math.Min(nix, S[i]);
}
else
{
int val = S[i];
// Loop to pop the element out
while (s.Count != 0 && val >= s.Peek())
{
s.Pop();
}
nix = Math.Min(nix, S[i]);
s.Push(nix);
}
}
// The size of the stack is the
// max no of subarrays for
// suffix till index i
// from the right
ans += s.Count;
}
return ans;
}
// Driver code
static void Main()
{
List<int> S = new List<int>();
S.Add(9);
S.Add(6);
S.Add(9);
S.Add(35);
Console.WriteLine(decompose(S));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript implementation to find the
// sum of Decomposition values of
// all suffixes of an array
// Function to find the decomposition
// values of the array
function decompose(S)
{
// Stack
let s = [];
let N = S.length;
let ans = 0;
// Variable to maintain
// min value in stack
let nix = Number.MAX_VALUE;
// Loop to iterate over the array
for(let i = N - 1; i >= 0; i--)
{
// Condition to check if the
// stack is empty
if (s.length==0)
{
s.push(S[i]);
nix = S[i];
}
else
{
// Condition to check if the
// top of the stack is greater
// than the current element
if (S[i] < s[s.length-1])
{
s.push(S[i]);
nix = Math.min(nix, S[i]);
}
else
{
let val = S[i];
// Loop to pop the element out
while (s.length!=0 && val >= s[s.length-1])
{
s.pop();
}
nix = Math.min(nix, S[i]);
s.push(nix);
}
}
// The size of the stack is the
// max no of subarrays for
// suffix till index i
// from the right
ans += s.length;
}
return ans;
}
// Driver Code
let S = [];
S.push(9);
S.push(6);
S.push(9);
S.push(35);
document.write(decompose(S));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
8
Publicación traducida automáticamente
Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA