Dada una array A[] , para cada elemento de la array, la tarea es encontrar la suma de todos los elementos anteriores que son estrictamente mayores que el elemento actual.
Ejemplos:
Entrada: A[] = {2, 6, 4, 1, 7}
Salida: 0 0 6 12 0
Explicación:
Para 2 y 6 no hay ningún elemento mayor a la izquierda.
Para 4 hay 6.
Para 1 la suma sería 12.
Para 7 tampoco hay elemento mayor que él.Entrada: A[] = {7, 3, 6, 2, 1}
Salida: 0 7 7 16 18
Explicación:
Para 7 no hay ningún elemento mayor a la izquierda.
Para 3 hay 7.
Para 6 la suma sería 7.
Para 2 tiene que ser 7 + 3 + 6 = 16.
Para 1 la suma sería 7 + 3 + 6 + 2 = 18
Enfoque ingenuo: para cada elemento, la idea es encontrar los elementos que son estrictamente mayores que el elemento actual en el lado izquierdo y luego encontrar la suma de todos esos elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Max Element of the Array
const int maxn = 1000000;
// Function to find the sum of previous
// numbers that are greater than the
// current number for the given array
void sumGreater(int ar[], int N)
{
// Loop to iterate over all
// the elements of the array
for (int i = 0; i < N; i++) {
// Store the answer for
// the current element
int cur_sum = 0;
// Iterate from (current index - 1)
// to 0 and check if ar[j] is greater
// than the current element and add
// it to the cur_sum if so
for (int j = i - 1; j >= 0; j--) {
if (ar[j] > ar[i])
cur_sum += ar[j];
}
// Print the answer for
// current element
cout << cur_sum << " ";
}
}
// Driver Code
int main()
{
// Given array arr[]
int ar[] = { 7, 3, 6, 2, 1 };
// Size of the array
int N = sizeof ar / sizeof ar[0];
// Function call
sumGreater(ar, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Max Element of the Array
static int maxn = 1000000;
// Function to find the sum of previous
// numbers that are greater than the
// current number for the given array
static void sumGreater(int ar[], int N)
{
// Loop to iterate over all
// the elements of the array
for(int i = 0; i < N; i++)
{
// Store the answer for
// the current element
int cur_sum = 0;
// Iterate from (current index - 1)
// to 0 and check if ar[j] is greater
// than the current element and add
// it to the cur_sum if so
for(int j = i - 1; j >= 0; j--)
{
if (ar[j] > ar[i])
cur_sum += ar[j];
}
// Print the answer for
// current element
System.out.print(cur_sum + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int ar[] = { 7, 3, 6, 2, 1 };
// Size of the array
int N = ar.length;
// Function call
sumGreater(ar, N);
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program for the above approach # Max Element of the Array maxn = 1000000; # Function to find the sum of previous # numbers that are greater than the # current number for the given array def sumGreater(ar, N): # Loop to iterate over all # the elements of the array for i in range(N): # Store the answer for # the current element cur_sum = 0; # Iterate from (current index - 1) # to 0 and check if ar[j] is greater # than the current element and add # it to the cur_sum if so for j in range(i, -1, -1): if (ar[j] > ar[i]): cur_sum += ar[j]; # Print the answer for # current element print(cur_sum, end = " "); # Driver Code if __name__ == '__main__': # Given array arr ar = [ 7, 3, 6, 2, 1] ; # Size of the array N = len(ar); # Function call sumGreater(ar, N); # This code is contributed by sapnasingh4991
C#
// C# program for the above approach
using System;
class GFG{
// Max Element of the Array
//static int maxn = 1000000;
// Function to find the sum of previous
// numbers that are greater than the
// current number for the given array
static void sumGreater(int []ar, int N)
{
// Loop to iterate over all
// the elements of the array
for(int i = 0; i < N; i++)
{
// Store the answer for
// the current element
int cur_sum = 0;
// Iterate from (current index - 1)
// to 0 and check if ar[j] is greater
// than the current element and add
// it to the cur_sum if so
for(int j = i - 1; j >= 0; j--)
{
if (ar[j] > ar[i])
cur_sum += ar[j];
}
// Print the answer for
// current element
Console.Write(cur_sum + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []ar = { 7, 3, 6, 2, 1 };
// Size of the array
int N = ar.Length;
// Function call
sumGreater(ar, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Max Element of the Array
var maxn = 1000000;
// Function to find the sum of previous
// numbers that are greater than the
// current number for the given array
function sumGreater(ar, N)
{
// Loop to iterate over all
// the elements of the array
for(i = 0; i < N; i++)
{
// Store the answer for
// the current element
var cur_sum = 0;
// Iterate from (current index - 1)
// to 0 and check if ar[j] is greater
// than the current element and add
// it to the cur_sum if so
for(j = i - 1; j >= 0; j--)
{
if (ar[j] > ar[i])
cur_sum += ar[j];
}
// Print the answer for
// current element
document.write(cur_sum + " ");
}
}
// Driver Code
// Given array arr
var ar = [ 7, 3, 6, 2, 1 ];
// Size of the array
var N = ar.length;
// Function call
sumGreater(ar, N);
// This code is contributed by umadevi9616
</script>
Producción:
0 7 7 16 18
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar Fenwick Tree . A continuación se muestran los pasos:
- Recorra la array dada y encuentre la suma (por ejemplo, total_sum ) de todos los elementos almacenados en el árbol de Fenwick.
- Ahora considere cada elemento (digamos arr[i] ) como el índice del árbol Fenwick.
- Ahora encuentre la suma de todos los elementos (por ejemplo, curr_sum ) que es más pequeña que el elemento actual usando los valores almacenados en Tree.
- El valor de total_sum – curr_sum dará la suma de todos los elementos que son estrictamente mayores que los elementos del lado izquierdo del elemento actual.
- Actualice el elemento actual en Fenwick Tree.
- Repita los pasos anteriores para todos los elementos de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Max Element of the Array
const int maxn = 1000000;
// Initializing Fenwick Tree
int Bit[maxn + 5];
// Function to calculate the sum of
// previous numbers that are greater
// than the current number in the array
void sum(int ar[], int N)
{
// Iterate from 1 to N
for (int i = 0; i < N; i++) {
int index;
int total_sum = 0;
index = 100000;
// If some greater values has
// occurred before current element
// then it will be already stored
// in Fenwick Tree
while (index) {
// Calculating sum of
// all the elements
total_sum += Bit[index];
index -= index & -index;
}
int cur_sum = 0;
// Sum only smaller or equal
// elements than current element
index = ar[i];
while (index) {
// If some smaller values has
// occurred before it will be
// already stored in Tree
cur_sum += Bit[index];
index -= (index & -index);
}
int ans = total_sum - cur_sum;
cout << ans << " ";
// Update the fenwick tree
index = ar[i];
while (index <= 100000) {
// Updating The Fenwick Tree
// for future values
Bit[index] += ar[i];
index += (index & -index);
}
}
}
// Driver Code
int main()
{
// Given array arr[]
int ar[] = { 7, 3, 6, 2, 1 };
int N = sizeof ar / sizeof ar[0];
// Function call
sum(ar, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Max Element of the Array
static int maxn = 1000000;
// Initializing Fenwick Tree
static int []Bit = new int[maxn + 5];
// Function to calculate the sum of
// previous numbers that are greater
// than the current number in the array
static void sum(int ar[], int N)
{
// Iterate from 1 to N
for (int i = 0; i < N; i++)
{
int index;
int total_sum = 0;
index = 100000;
// If some greater values has
// occurred before current element
// then it will be already stored
// in Fenwick Tree
while (index > 0)
{
// Calculating sum of
// all the elements
total_sum += Bit[index];
index -= index & -index;
}
int cur_sum = 0;
// Sum only smaller or equal
// elements than current element
index = ar[i];
while (index > 0)
{
// If some smaller values has
// occurred before it will be
// already stored in Tree
cur_sum += Bit[index];
index -= (index & -index);
}
int ans = total_sum - cur_sum;
System.out.print(ans + " ");
// Update the fenwick tree
index = ar[i];
while (index <= 100000)
{
// Updating The Fenwick Tree
// for future values
Bit[index] += ar[i];
index += (index & -index);
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int ar[] = { 7, 3, 6, 2, 1 };
int N = ar.length;
// Function call
sum(ar, N);
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach # Max Element of the Array maxn = 1000000; # Initializing Fenwick Tree Bit = [0] * (maxn + 5); # Function to calculate the sum of # previous numbers that are greater # than the current number in the array def sum(ar, N): # Iterate from 1 to N for i in range(N): total_sum = 0; index = 100000; # If some greater values has # occurred before current element # then it will be already stored # in Fenwick Tree while (index > 0): # Calculating sum of # all the elements total_sum += Bit[index]; index -= index & -index; cur_sum = 0; # Sum only smaller or equal # elements than current element index = ar[i]; while (index > 0): # If some smaller values has # occurred before it will be # already stored in Tree cur_sum += Bit[index]; index -= (index & -index); ans = total_sum - cur_sum; print(ans, end=" "); # Update the fenwick tree index = ar[i]; while (index <= 100000): # Updating The Fenwick Tree # for future values Bit[index] += ar[i]; index += (index & -index); # Driver Code if __name__ == '__main__': # Given array arr arr = [7, 3, 6, 2, 1]; N = len(arr); # Function call sum(arr, N); # This code is contributed by sapnasingh4991
C#
// C# program for the above approach
using System;
class GFG{
// Max Element of the Array
static int maxn = 1000000;
// Initializing Fenwick Tree
static int []Bit = new int[maxn + 5];
// Function to calculate the sum of
// previous numbers that are greater
// than the current number in the array
static void sum(int []ar, int N)
{
// Iterate from 1 to N
for (int i = 0; i < N; i++)
{
int index;
int total_sum = 0;
index = 100000;
// If some greater values has
// occurred before current element
// then it will be already stored
// in Fenwick Tree
while (index > 0)
{
// Calculating sum of
// all the elements
total_sum += Bit[index];
index -= index & -index;
}
int cur_sum = 0;
// Sum only smaller or equal
// elements than current element
index = ar[i];
while (index > 0)
{
// If some smaller values has
// occurred before it will be
// already stored in Tree
cur_sum += Bit[index];
index -= (index & -index);
}
int ans = total_sum - cur_sum;
Console.Write(ans + " ");
// Update the fenwick tree
index = ar[i];
while (index <= 100000)
{
// Updating The Fenwick Tree
// for future values
Bit[index] += ar[i];
index += (index & -index);
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []ar = { 7, 3, 6, 2, 1 };
int N = ar.Length;
// Function call
sum(ar, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program for the above approach
// Max Element of the Array
var maxn = 1000000;
// Initializing Fenwick Tree
var Bit = Array(maxn + 5).fill(0);
// Function to calculate the sum of
// previous numbers that are greater
// than the current number in the array
function sum(ar , N) {
// Iterate from 1 to N
for (i = 0; i < N; i++) {
var index;
var total_sum = 0;
index = 100000;
// If some greater values has
// occurred before current element
// then it will be already stored
// in Fenwick Tree
while (index > 0) {
// Calculating sum of
// all the elements
total_sum += Bit[index];
index -= index & -index;
}
var cur_sum = 0;
// Sum only smaller or equal
// elements than current element
index = ar[i];
while (index > 0) {
// If some smaller values has
// occurred before it will be
// already stored in Tree
cur_sum += Bit[index];
index -= (index & -index);
}
var ans = total_sum - cur_sum;
document.write(ans + " ");
// Update the fenwick tree
index = ar[i];
while (index <= 100000) {
// Updating The Fenwick Tree
// for future values
Bit[index] += ar[i];
index += (index & -index);
}
}
}
// Driver Code
// Given array arr
var ar = [ 7, 3, 6, 2, 1 ];
var N = ar.length;
// Function call
sum(ar, N);
// This code contributed by aashish1995
</script>
Producción:
0 7 7 16 18
Complejidad de tiempo: O(N * log(max_element))
Espacio auxiliar: O(max_element)
Publicación traducida automáticamente
Artículo escrito por dbarnwal888 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA