Minimice las operaciones de incremento para que Array no sea decreciente

Dada una array arr[] de n enteros. Modifique la array de modo que cada elemento sea al menos tan grande como el elemento anterior. Esto se puede hacer aumentando el valor de cualquier elemento en 1 . La tarea es encontrar el número mínimo de movimientos necesarios para que la array no disminuya.

Ejemplos:

Entrada: n = 5, arr[] = {8, 9, 2, 7, 7}
Salida: 11
Explicación: La array debe modificarse a 8 9 9 9 9, esto se puede hacer con 11 movimientos (7 + 2 + 2).

Entrada: n = 10, arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} Salida:
0 Explicación
: La array ya no es decreciente.

Enfoque: la idea es atravesar la array y en cualquier punto cuando el elemento actual es más pequeño que el anterior, luego hacer que el actual sea como el anterior y aumentar la cuenta. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable count como 0 para almacenar el resultado.
• Itere sobre el rango [0, n) usando la variable i y realice las siguientes tareas:
  • Si arr[i] es menor que arr[i-1] , establezca el valor de arr[i] como arr[i-1] y aumente el valor de count en arr[i]-arr[i-1].
• Después de realizar los pasos anteriores, imprima el valor de conteo como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// value of count
long long countMoves(long int arr[], int n)
{
 
    // Variable to store the answer
    long int count = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
        if (i > 0) {
 
            // Make the changes
            if (arr[i] < arr[i - 1]) {
                count += (arr[i - 1] - arr[i]);
                arr[i] = arr[i - 1];
            }
        }
    }
 
    // Return the answer
    return count;
}
 
// Driver Code
int main()
{
 
    int n = 5;
 
    long int arr[] = { 8, 9, 2, 7, 7 };
 
    cout << countMoves(arr, n);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
  // Function to find the minimum
  // value of count
  static long countMoves(int arr[], int n)
  {
 
    // Variable to store the answer
    int count = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
      if (i > 0) {
 
        // Make the changes
        if (arr[i] < arr[i - 1]) {
          count += (arr[i - 1] - arr[i]);
          arr[i] = arr[i - 1];
        }
      }
    }
 
    // Return the answer
    return count;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    int n = 5;
 
    int arr[] = { 8, 9, 2, 7, 7 };
 
    System.out.print(countMoves(arr, n));
  }
}
 
// This code is contributed by 29AjayKumar

# Python code for the above approach
 
# Function to find the minimum
# value of count
def countMoves(arr, n):
 
    # Variable to store the answer
    count = 0
 
    # Traverse the array
    for i in range(n):
        if (i > 0):
 
            # Make the changes
            if (arr[i] < arr[i - 1]):
                count += (arr[i - 1] - arr[i])
                arr[i] = arr[i - 1]
 
    # Return the answer
    return count
 
# Driver Code
n = 5
arr = [8, 9, 2, 7, 7]
print(countMoves(arr, n))
 
# This code is contributed by gfgking

// C# code to implement above approach
using System;
class GFG
{
 
  // Function to find the minimum
  // value of count
  static long countMoves(int []arr, int n)
  {
 
    // Variable to store the answer
    int count = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
      if (i > 0) {
 
        // Make the changes
        if (arr[i] < arr[i - 1]) {
          count += (arr[i - 1] - arr[i]);
          arr[i] = arr[i - 1];
        }
      }
    }
 
    // Return the answer
    return count;
  }
 
  // Driver code
  public static void Main()
  {
    int n = 5;
 
    int []arr = { 8, 9, 2, 7, 7 };
 
    Console.Write(countMoves(arr, n));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
      // JavaScript code for the above approach
 
      // Function to find the minimum
      // value of count
      function countMoves(arr, n) {
 
          // Variable to store the answer
          let count = 0;
 
          // Traverse the array
          for (let i = 0; i < n; i++) {
              if (i > 0) {
 
                  // Make the changes
                  if (arr[i] < arr[i - 1]) {
                      count += (arr[i - 1] - arr[i]);
                      arr[i] = arr[i - 1];
                  }
              }
          }
 
          // Return the answer
          return count;
      }
 
      // Driver Code
      let n = 5;
      let arr = [8, 9, 2, 7, 7];
 
      document.write(countMoves(arr, n));
       
// This code is contributed by Potta Lokesh
  </script>

11

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