Dada una array a[] que consta de N enteros, la tarea es encontrar la suma máxima posible que se puede lograr al deducir cualquier valor, digamos X , de todos los elementos de una subarreferencia.
Ejemplos:
Entrada: N = 3, a[] = {80, 48, 82}
Salida: 144
Explicación:
48 se pueden deducir de cada elemento de la array. Por lo tanto, suma obtenida = 48 * 3 = 144
Entrada: N = a[] = {8, 40, 77}
Salida: 80
Explicación:
Restar 8 de todos los elementos del arreglo genera la suma 24.
Restar 40 de arr[1] y arr[ 2] genera suma 80.
Restar 77 de arr[2] genera suma 77.
Por lo tanto, la suma máxima posible es 80.
Enfoque:
siga los pasos a continuación para resolver el problema:
- Atraviesa la array
- Para cada elemento, encuentre el elemento más pequeño más cercano a su izquierda y más pequeño a su derecha.
- Calcule la suma posible por ese elemento calculando current_element * ( j – i – 1 ) donde j e i son los índices de los números más pequeños más cercanos a la izquierda y derecha respectivamente.
- Encuentra la suma máxima posible entre todos ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate previous smaller
// element for each array element
vector<int> findPrevious(vector<int> a, int n)
{
vector<int> ps(n);
// The first element has no
// previous smaller
ps[0] = -1;
// Stack to keep track of elements
// that have occurred previously
stack<int> Stack;
// Push the first index
Stack.push(0);
for(int i = 1; i < n; i++)
{
// Pop all the elements until the previous
// element is smaller than current element
while (Stack.size() > 0 &&
a[Stack.top()] >= a[i])
Stack.pop();
// Store the previous smaller element
ps[i] = Stack.size() > 0 ?
Stack.top() : -1;
// Push the index of the current element
Stack.push(i);
}
// Return the array
return ps;
}
// Function to generate next smaller element
// for each array element
vector<int> findNext(vector<int> a, int n)
{
vector<int> ns(n);
ns[n - 1] = n;
// Stack to keep track of elements
// that have occurring next
stack<int> Stack;
Stack.push(n - 1);
// Iterate in reverse order
// for calculating next smaller
for(int i = n - 2; i >= 0; i--)
{
// Pop all the elements until the
// next element is smaller
// than current element
while (Stack.size() > 0 &&
a[Stack.top()] >= a[i])
Stack.pop();
// Store the next smaller element
ns[i] = Stack.size() > 0 ?
Stack.top() : n;
// Push the index of the current element
Stack.push(i);
}
// Return the array
return ns;
}
// Function to find the maximum sum by
// subtracting same value from all
// elements of a Subarray
int findMaximumSum(vector<int> a, int n)
{
// Stores previous smaller element
vector<int> prev_smaller = findPrevious(a, n);
// Stores next smaller element
vector<int> next_smaller = findNext(a, n);
int max_value = 0;
for(int i = 0; i < n; i++)
{
// Calculate contribution
// of each element
max_value = max(max_value, a[i] *
(next_smaller[i] -
prev_smaller[i] - 1));
}
// Return answer
return max_value;
}
// Driver Code
int main()
{
int n = 3;
vector<int> a{ 80, 48, 82 };
cout << findMaximumSum(a, n);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java Program to implement
// the above approach
import java.util.*;
public class GFG {
// Function to find the maximum sum by
// subtracting same value from all
// elements of a Subarray
public static int findMaximumSum(int[] a, int n)
{
// Stores previous smaller element
int prev_smaller[] = findPrevious(a, n);
// Stores next smaller element
int next_smaller[] = findNext(a, n);
int max_value = 0;
for (int i = 0; i < n; i++) {
// Calculate contribution
// of each element
max_value
= Math.max(max_value,
a[i] * (next_smaller[i]
- prev_smaller[i] - 1));
}
// Return answer
return max_value;
}
// Function to generate previous smaller element
// for each array element
public static int[] findPrevious(int[] a, int n)
{
int ps[] = new int[n];
// The first element has no
// previous smaller
ps[0] = -1;
// Stack to keep track of elements
// that have occurred previously
Stack<Integer> stack = new Stack<>();
// Push the first index
stack.push(0);
for (int i = 1; i < a.length; i++) {
// Pop all the elements until the previous
// element is smaller than current element
while (stack.size() > 0
&& a[stack.peek()] >= a[i])
stack.pop();
// Store the previous smaller element
ps[i] = stack.size() > 0 ? stack.peek() : -1;
// Push the index of the current element
stack.push(i);
}
// Return the array
return ps;
}
// Function to generate next smaller element
// for each array element
public static int[] findNext(int[] a, int n)
{
int ns[] = new int[n];
ns[n - 1] = n;
// Stack to keep track of elements
// that have occurring next
Stack<Integer> stack = new Stack<>();
stack.push(n - 1);
// Iterate in reverse order
// for calculating next smaller
for (int i = n - 2; i >= 0; i--) {
// Pop all the elements until the
// next element is smaller
// than current element
while (stack.size() > 0
&& a[stack.peek()] >= a[i])
stack.pop();
// Store the next smaller element
ns[i] = stack.size() > 0 ? stack.peek()
: a.length;
// Push the index of the current element
stack.push(i);
}
// Return the array
return ns;
}
// Driver Code
public static void main(String args[])
{
int n = 3;
int a[] = { 80, 48, 82 };
System.out.println(findMaximumSum(a, n));
}
}
Python3
# Python3 program to implement # the above approach # Function to find the maximum sum by # subtracting same value from all # elements of a Subarray def findMaximumSum(a, n): # Stores previous smaller element prev_smaller = findPrevious(a, n) # Stores next smaller element next_smaller = findNext(a, n) max_value = 0 for i in range(n): # Calculate contribution # of each element max_value = max(max_value, a[i] * (next_smaller[i] - prev_smaller[i] - 1)) # Return answer return max_value # Function to generate previous smaller # element for each array element def findPrevious(a, n): ps = [0] * n # The first element has no # previous smaller ps[0] = -1 # Stack to keep track of elements # that have occurred previously stack = [] # Push the first index stack.append(0) for i in range(1, n): # Pop all the elements until the previous # element is smaller than current element while len(stack) > 0 and a[stack[-1]] >= a[i]: stack.pop() # Store the previous smaller element ps[i] = stack[-1] if len(stack) > 0 else -1 # Push the index of the current element stack.append(i) # Return the array return ps # Function to generate next smaller # element for each array element def findNext(a, n): ns = [0] * n ns[n - 1] = n # Stack to keep track of elements # that have occurring next stack = [] stack.append(n - 1) # Iterate in reverse order # for calculating next smaller for i in range(n - 2, -1, -1): # Pop all the elements until the # next element is smaller # than current element while (len(stack) > 0 and a[stack[-1]] >= a[i]): stack.pop() # Store the next smaller element ns[i] = stack[-1] if len(stack) > 0 else n # Push the index of the current element stack.append(i) # Return the array return ns # Driver code n = 3 a = [ 80, 48, 82 ] print(findMaximumSum(a, n)) # This code is contributed by Stuti Pathak
C#
// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum sum by
// subtracting same value from all
// elements of a Subarray
public static int findMaximumSum(int[] a, int n)
{
// Stores previous smaller element
int []prev_smaller = findPrevious(a, n);
// Stores next smaller element
int []next_smaller = findNext(a, n);
int max_value = 0;
for (int i = 0; i < n; i++)
{
// Calculate contribution
// of each element
max_value = Math.Max(max_value,
a[i] * (next_smaller[i] -
prev_smaller[i] - 1));
}
// Return answer
return max_value;
}
// Function to generate previous smaller element
// for each array element
public static int[] findPrevious(int[] a, int n)
{
int []ps = new int[n];
// The first element has no
// previous smaller
ps[0] = -1;
// Stack to keep track of elements
// that have occurred previously
Stack<int> stack = new Stack<int>();
// Push the first index
stack.Push(0);
for (int i = 1; i < a.Length; i++)
{
// Pop all the elements until the previous
// element is smaller than current element
while (stack.Count > 0 &&
a[stack.Peek()] >= a[i])
stack.Pop();
// Store the previous smaller element
ps[i] = stack.Count > 0 ? stack.Peek() : -1;
// Push the index of the current element
stack.Push(i);
}
// Return the array
return ps;
}
// Function to generate next smaller element
// for each array element
public static int[] findNext(int[] a, int n)
{
int []ns = new int[n];
ns[n - 1] = n;
// Stack to keep track of elements
// that have occurring next
Stack<int> stack = new Stack<int>();
stack.Push(n - 1);
// Iterate in reverse order
// for calculating next smaller
for (int i = n - 2; i >= 0; i--)
{
// Pop all the elements until the
// next element is smaller
// than current element
while (stack.Count > 0 &&
a[stack.Peek()] >= a[i])
stack.Pop();
// Store the next smaller element
ns[i] = stack.Count > 0 ? stack.Peek()
: a.Length;
// Push the index of the current element
stack.Push(i);
}
// Return the array
return ns;
}
// Driver Code
public static void Main(String []args)
{
int n = 3;
int []a = { 80, 48, 82 };
Console.WriteLine(findMaximumSum(a, n));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript Program to implement
// the above approach
// Function to find the maximum sum by
// subtracting same value from all
// elements of a Subarray
function findMaximumSum(a ,n)
{
// Stores previous smaller element
var prev_smaller = findPrevious(a, n);
// Stores next smaller element
var next_smaller = findNext(a, n);
var max_value = 0;
for (var i = 0; i < n; i++)
{
// Calculate contribution
// of each element
max_value = Math.max(max_value, a[i] * (next_smaller[i] - prev_smaller[i] - 1));
}
// Return answer
return max_value;
}
// Function to generate previous smaller element
// for each array element
function findPrevious(a , n) {
var ps = Array(n).fill(0);
// The first element has no
// previous smaller
ps[0] = -1;
// Stack to keep track of elements
// that have occurred previously
let stack = Array();
// Push the first index
stack.push(0);
for (var i = 1; i < a.length; i++) {
// Pop all the elements until the previous
// element is smaller than current element
while (stack.length > 0 && a[stack[stack.length-1]] >= a[i])
stack.pop();
// Store the previous smaller element
ps[i] = stack.length > 0 ?stack[stack.length-1] : -1;
// Push the index of the current element
stack.push(i);
}
// Return the array
return ps;
}
// Function to generate next smaller element
// for each array element
function findNext(a , n) {
var ns = Array(n).fill(0);
ns[n - 1] = n;
// Stack to keep track of elements
// that have occurring next
var stack = Array();
stack.push(n - 1);
// Iterate in reverse order
// for calculating next smaller
for (var i = n - 2; i >= 0; i--) {
// Pop all the elements until the
// next element is smaller
// than current element
while (stack.length > 0 && a[stack[stack.length-1]] >= a[i])
stack.pop();
// Store the next smaller element
ns[i] = stack.length > 0 ? stack[stack.length-1] : a.length;
// Push the index of the current element
stack.push(i);
}
// Return the array
return ns;
}
// Driver Code
var n = 3;
var a = [ 80, 48, 82 ];
document.write(findMaximumSum(a, n));
// This code is contributed by gauravrajput1
</script>
Producción:
144
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA