Decrementos mínimos en los subarreglos necesarios para reducir todos los elementos del arreglo a cero

Dada una array arr[] que consta de N enteros no negativos, la tarea es encontrar el número mínimo de subarreglos que deben reducirse en 1 de modo que todos los elementos de la array sean iguales a 0.

Ejemplo:

Entrada: arr[] = {1, 2, 3, 2, 1}
Salida: 3
Explicación: 
Operación 1: {1, 2, 3, 2, 1} -> {0, 1, 2, 1, 0} 
Operación 2: {0, 1, 2, 1, 0} -> {0, 0, 1, 0, 0} 
Operación 3: {0, 0, 1, 0, 0} -> {0, 0, 0, 0 , 0}

Entrada: arr[] = {5, 4, 3, 4, 4}
Salida: 6
Explicación: 
{5, 4, 3, 4, 4} -> {4, 3, 2, 3, 3} -> {3 , 2, 1, 2, 2} -> {2, 1, 0, 1, 1} -> {2, 1, 0, 0, 0} -> {1, 0, 0, 0, 0} -> {0, 0, 0, 0, 0} 
 

Enfoque: 
esto se puede hacer de manera óptima atravesando la array dada desde el índice 0 , encontrando la respuesta hasta el índice i , donde 0 ≤ i < N. Si arr[i] ≥ arr[i+1] , entonces (i + 1) el elemento ^th se puede incluir en cada operación de subarreglo del elemento i ^th , por lo que no requiere operaciones adicionales. Si arr[i] < arr[i + 1] , entonces (i + 1) el elemento ^th se puede incluir en cada operación de subarreglo del i ^th elemento y después de todas las operaciones, arr[i+1] se convierte en arr[i+1] -arr[yo] . Por lo tanto, necesitamos arr[i+1]-arr[i]operaciones extra para reducirlo a cero.

Siga los pasos a continuación para resolver el problema:

• Agregue el primer elemento arr[0] para responder , ya que necesitamos al menos arr[0] para hacer que la array dada sea 0 .
• Recorra los índices [1, N-1] y para cada elemento, verifique si es mayor que el elemento anterior. Si se encuentra que es cierto, agregue su diferencia a la respuesta .

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

// C++ Program to implement 
// the above approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to count the minimum 
// number of subarrays that are 
// required to be decremented by 1 
int min_operations(vector<int>& A) 
{ 
    // Base Case 
    if (A.size() == 0) 
        return 0; 
  
    // Initialize ans to first element 
    int ans = A[0]; 
  
    for (int i = 1; i < A.size(); i++) { 
  
        // For A[i] > A[i-1], operation 
        // (A[i] - A[i - 1]) is required 
        ans += max(A[i] - A[i - 1], 0); 
    } 
  
    // Return the answer 
    return ans; 
} 
  
// Driver Code 
int main() 
{ 
    vector<int> A{ 1, 2, 3, 2, 1 }; 
  
    cout << min_operations(A) << "\n"; 
  
    return 0; 
} 

// Java Program to implement 
// the above approach 
import java.io.*; 
  
class GFG { 
  
    // Function to count the minimum 
    // number of subarrays that are 
    // required to be decremented by 1 
    static int min_operations(int A[], int n) 
    { 
        // Base Case 
        if (n == 0) 
            return 0; 
  
        // Initializing ans to first element 
        int ans = A[0]; 
        for (int i = 1; i < n; i++) { 
  
            // For A[i] > A[i-1], operation 
            // (A[i] - A[i - 1]) is required 
            if (A[i] > A[i - 1]) { 
                ans += A[i] - A[i - 1]; 
            } 
        } 
  
        // Return the count 
        return ans; 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        int n = 5; 
        int A[] = { 1, 2, 3, 2, 1 }; 
        System.out.println(min_operations(A, n)); 
    } 
} 

# Python Program to implement 
# the above approach 
  
# Function to count the minimum 
# number of subarrays that are 
# required to be decremented by 1 
def min_operations(A): 
  
    # Base case 
    if len(A) == 0: 
        return 0
  
    # Initializing ans to first element 
    ans = A[0] 
    for i in range(1, len(A)): 
  
        if A[i] > A[i-1]: 
            ans += A[i]-A[i-1] 
  
    return ans 
  
  
# Driver Code 
A = [1, 2, 3, 2, 1] 
print(min_operations(A)) 

// C# program to implement
// the above approach
using System;
  
class GFG{
  
// Function to count the minimum
// number of subarrays that are
// required to be decremented by 1
static int min_operations(int[] A, int n)
{
      
    // Base Case
    if (n == 0)
        return 0;
  
    // Initializing ans to first element
    int ans = A[0];
      
    for(int i = 1; i < n; i++) 
    {
          
        // For A[i] > A[i-1], operation
        // (A[i] - A[i - 1]) is required
        if (A[i] > A[i - 1]) 
        {
            ans += A[i] - A[i - 1];
        }
    }
      
    // Return the count
    return ans;
}
  
// Driver Code
public static void Main()
{
    int n = 5;
    int[] A = { 1, 2, 3, 2, 1 };
      
    Console.WriteLine(min_operations(A, n));
}
}
  
// This code is contributed by bolliranadheer

<script>
  
// Javascript program to implement 
// the above approach 
  
// Function to count the minimum 
// number of subarrays that are 
// required to be decremented by 1 
function min_operations(A) 
{ 
      
    // Base Case 
    if (A.length == 0) 
        return 0; 
  
    // Initialize ans to first element 
    let ans = A[0]; 
  
    for(let i = 1; i < A.length; i++)
    { 
          
        // For A[i] > A[i-1], operation 
        // (A[i] - A[i - 1]) is required 
        ans += Math.max(A[i] - A[i - 1], 0); 
    } 
  
    // Return the answer 
    return ans; 
} 
  
// Driver Code 
let A = [ 1, 2, 3, 2, 1 ]; 
document.write(min_operations(A)); 
  
// This code is contributed by subhammahato348
  
</script>

Producción:

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array