Maximizar la suma de la array dada después de eliminar los valles

Posted on by Rudeus Greyrat

Dada una array arr[] de enteros de tamaño N, la tarea es maximizar la suma de la array después de eliminar los valles de la array cuando solo se permite reducir el valor de un elemento, es decir, la nueva array formada no debe contener ningún elemento que tenga mayor valor después de la modificación.

Valles :- Un índice j se considera como un punto de valle si   arr[i] > arr[j] y arr[ k ] > arr[ j ]  dado que ( i < j < k ).

Ejemplos : 

Entrada : arr[] = { 5, 10, 15 }
Salida : 30 
Explicación : Como la array no contiene ningún valle, no hay necesidad de reducir ningún elemento.

Entrada : arr[] = { 8, 1, 10, 1, 8 }
Salida : 14   
Explicación: new_arr=> [1, 1, 10, 1, 1] y sum = 14, new_arr también se puede construir como [8, 1, 1, 1, 1], pero la suma será menor.

 

Enfoque ingenuo : Considere cada elemento como un elemento pico y comience en orden decreciente en ambas direcciones del elemento pico. 
 

Si arr = [8, 1, 10, 1, 8] 
Considere 10 como elemento pico y luego la array final sería [1, 1, 10, 1, 1]

Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar :O(1)

Enfoque eficiente : en lugar de tomar cada índice como un punto máximo. Calcule la array de suma de prefijos y sufijos para cada índice (idx). La array de prefijos se puede usar para almacenar la suma de alturas desde 0 . . . idx cumple la condición de que no hay valle en el lado izquierdo e idx tiene el elemento pico. La array de suma de sufijos también satisface las mismas condiciones para el sufijo del índice idx . 

El elemento en un índice puede abarcar en la dirección izquierda, hasta que se encuentre un elemento más pequeño, asumiendo que el elemento actual es el más alto. El siguiente elemento más pequeño que usa el concepto de pila se puede usar aquí con cambios menores.

Siga los pasos que se mencionan a continuación:

  • Cree la array de suma de prefijos (izquierda) y suma de sufijos (derecha) . Habrá dos casos al construir las arrays. Considere los casos para la array de suma de prefijos a continuación. Lo mismo es aplicable para la array de suma de sufijos también.
    1. El elemento actual es el más pequeño entre todos los elementos hasta ahora.
      Entonces, izquierda [ curr_idx ] = ( i +1 ) * arr[i]  . Aquí (i + 1) denota el rango.
    2. Hay un elemento más pequeño con small_idx , en el lado izquierdo.
      Entonces, left [curr_idx] = left[small_idx] + (current_idx – small_idx) *arr[i]
      Usando el mismo método se puede calcular la array de suma derecha .
  • Ahora, itere a través de cada índice y calcule la respuesta = izquierda [idx] + derecha [idx] – arr [idx]

Nota: arr[idx] se resta, porque arr[idx] se agrega en la array izquierda[] y derecha[] .

Consulte la siguiente ilustración para una mejor comprensión.

Ilustración:

Considere el ejemplo   arr[] = { 5, 1, 8 } 
Mientras crea la array de suma de prefijos 
En índice = 0: No hay ningún elemento en el lado izquierdo [0] = 5.
Índice = 1: 1 es el más pequeño entre todos los izquierda. Entonces, izquierda[1] = 1 * 2 = 2. 
Índice = 2: 8 tiene el elemento 1 más pequeño en el índice 1. Entonces izquierda[2] = izquierda[1] + 8*(2 – 1) = 2 + 8 = 10
Entonces izquierda[] = {5, 2, 10} . Del mismo modo derecho[] = {7, 2, 8}.
Ahora, mientras se desplaza para calcular la respuesta, los valores del índice 0, 1 y 2 son (5 + 7 – 5), (2 + 2 – 1), (10 + 8 – 8) respectivamente. El máximo entre estos es 10. Entonces la respuesta es 10.

 A continuación se muestra la implementación del enfoque anterior:

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to get get the maximum cost
int solve(vector<int>& arr)
{
  int n = arr.size();
  vector<int> left(n, 0);
  vector<int> right(n, 0);
  vector<int> stack;
 
  // Calculate left array
  for (int i = 0; i < n; i++) {
    int curr = arr[i];
    while (stack.size() != 0
           && arr[stack[stack.size() - 1]] >= curr) {
      stack.pop_back();
    }
    // Case 1
    if (stack.size() == 0)
      left[i] = (i + 1) * (arr[i]);
 
    // Case 2
    else {
      int small_idx = stack[stack.size() - 1];
      left[i] = left[small_idx]
        + (i - small_idx) * (arr[i]);
    }
    stack.push_back(i);
  }
  stack.clear();
 
  // Calculate suffix sum array
  for (int i = n - 1; i > -1; i--) {
    int curr = arr[i];
    while (stack.size() != 0
           && arr[stack[stack.size() - 1]] >= curr) {
      stack.pop_back();
    }
 
    if (stack.size() == 0)
      right[i] = (n - i) * (arr[i]);
 
    else {
      int small_idx = stack[stack.size() - 1];
      right[i] = right[small_idx]
        + (small_idx - i) * (arr[i]);
    }
    stack.push_back(i);
  }
  int ans = 0;
 
  for (int i = 0; i < n; i++) {
    int curr = left[i] + right[i] - arr[i];
    ans = max(ans, curr);
  }
  return (ans);
}
 
// Driver code
int main()
{
  vector<int> arr = { 5, 1, 8 };
  cout << solve(arr);
 
  return 0;
}
 
// This code is contributed by rakeshsahni

Java

// Java code for the above approach
import java.util.*;
class GFG{
 
// Function to get get the maximum cost
static int solve(int[] arr)
{
  int n = arr.length;
  int []left = new int[n];
  int []right = new int[n];
  Vector<Integer> stack = new Vector<Integer>();
 
  // Calculate left array
  for (int i = 0; i < n; i++) {
    int curr = arr[i];
    while (stack.size() != 0
           && arr[stack.get(stack.size() - 1)] >= curr) {
      stack.remove(stack.size() - 1);
    }
    // Case 1
    if (stack.size() == 0)
      left[i] = (i + 1) * (arr[i]);
 
    // Case 2
    else {
      int small_idx = stack.get(stack.size() - 1);
      left[i] = left[small_idx]
        + (i - small_idx) * (arr[i]);
    }
    stack.add(i);
  }
  stack.clear();
 
  // Calculate suffix sum array
  for (int i = n - 1; i > -1; i--) {
    int curr = arr[i];
    while (stack.size() != 0
           && arr[stack.get(stack.size() - 1)] >= curr) {
        stack.remove(stack.size() - 1);
    }
 
    if (stack.size() == 0)
      right[i] = (n - i) * (arr[i]);
 
    else {
      int small_idx = stack.get(stack.size() - 1);
      right[i] = right[small_idx]
        + (small_idx - i) * (arr[i]);
    }
    stack.add(i);
  }
  int ans = 0;
 
  for (int i = 0; i < n; i++) {
    int curr = left[i] + right[i] - arr[i];
    ans = Math.max(ans, curr);
  }
  return (ans);
}
 
// Driver code
public static void main(String[] args)
{
  int[] arr = { 5, 1, 8 };
  System.out.print(solve(arr));
 
}
}
 
// This code is contributed by 29AjayKumar.

Python3

# Python code to implement above approach
 
# Function to get get the maximum cost
def solve(arr):
    n = len(arr)
    left = [0]*(n)
    right = [0]*(n)
    stack = []
 
    # Calculate left array
    for i in range(n):
        curr = arr[i]
        while(stack and
              arr[stack[-1]] >= curr):
            stack.pop()
 
        # Case 1
        if (len(stack) == 0):
            left[i] = (i + 1)*(arr[i])
 
        # Case 2
        else:
            small_idx = stack[-1]
            left[i] = left[small_idx] \
                     + (i - small_idx)*(arr[i])
        stack.append(i)
 
    stack.clear()
 
    # Calculate suffix sum array
    for i in range(n-1, -1, -1):
        curr = arr[i]
        while(stack and
              arr[stack[-1]] >= curr):
            stack.pop()
 
        if (len(stack) == 0):
            right[i] = (n-i)*(arr[i])
 
        else:
            small_idx = stack[-1]
            right[i] = right[small_idx] \
                     + (small_idx - i)*(arr[i])
 
        stack.append(i)
 
    ans = 0
 
    for i in range(n):
        curr = left[i] + right[i] - arr[i]
        ans = max(ans, curr)
 
    return (ans)
 
# Driver code
if __name__ == "__main__":
    arr = [5, 1, 8]
    print(solve(arr))

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to get get the maximum cost
  static int solve(int[] arr)
  {
    int n = arr.Length;
    int[] left = new int[n];
    int[] right = new int[n];
    List<int> stack = new List<int>();
 
    // Calculate left array
    for (int i = 0; i < n; i++) {
      int curr = arr[i];
      while (stack.Count != 0
             && arr[stack[stack.Count - 1]] >= curr) {
        stack.RemoveAt(stack.Count - 1);
      }
 
      // Case 1
      if (stack.Count == 0)
        left[i] = (i + 1) * (arr[i]);
 
      // Case 2
      else {
        int small_idx = stack[stack.Count - 1];
        left[i] = left[small_idx]
          + (i - small_idx) * (arr[i]);
      }
      stack.Add(i);
    }
    stack.Clear();
 
    // Calculate suffix sum array
    for (int i = n - 1; i > -1; i--) {
      int curr = arr[i];
      while (stack.Count != 0
             && arr[stack[stack.Count - 1]] >= curr) {
        stack.RemoveAt(stack.Count - 1);
      }
 
      if (stack.Count == 0)
        right[i] = (n - i) * (arr[i]);
 
      else {
        int small_idx = stack[stack.Count - 1];
        right[i] = right[small_idx]
          + (small_idx - i) * (arr[i]);
      }
      stack.Add(i);
    }
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
      int curr = left[i] + right[i] - arr[i];
      ans = Math.Max(ans, curr);
    }
    return (ans);
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int[] arr = { 5, 1, 8 };
    Console.WriteLine(solve(arr));
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript code for the above approach
 
        // Function to get get the maximum cost
        function solve(arr) {
            let n = arr.length
            let left = new Array(n).fill(0)
            let right = new Array(n).fill(0)
            let stack = []
 
            // Calculate left array
            for (let i = 0; i < n; i++) {
                curr = arr[i]
                while (stack.length != 0 &&
                    arr[stack[stack.length - 1]] >= curr) {
                    stack.pop()
                }
                // Case 1
                if (stack.length == 0)
                    left[i] = (i + 1) * (arr[i])
 
                // Case 2
                else {
                    small_idx = stack[stack.length - 1]
                    left[i] = left[small_idx]
                        + (i - small_idx) * (arr[i])
                }
                stack.push(i)
            }
            stack = []
 
            // Calculate suffix sum array
            for (let i = n - 1; i > -1; i--) {
                curr = arr[i]
                while (stack.length != 0 &&
                    arr[stack[stack.length - 1]] >= curr) {
                    stack.pop()
                }
 
                if (stack.length == 0)
                    right[i] = (n - i) * (arr[i])
 
                else {
                    small_idx = stack[stack.length - 1]
                    right[i] = right[small_idx]
                        + (small_idx - i) * (arr[i])
                }
                stack.push(i)
            }
            ans = 0
 
            for (let i = 0; i < n; i++) {
                curr = left[i] + right[i] - arr[i]
                ans = Math.max(ans, curr)
            }
            return (ans)
        }
         
        // Driver code
        arr = [5, 1, 8]
        document.write(solve(arr))
 
  // This code is contributed by Potta Lokesh
    </script>
Producción

10

Tiempo Complejidad : O(N)
Espacio Auxiliar :O(N)

Publicación traducida automáticamente

Artículo escrito por chantya17 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *