Operaciones de incremento de rango mínimo para ordenar una array

Dada una array que contiene N elementos. Está permitido hacer el siguiente movimiento cualquier cantidad de veces en la array: 

• Elija cualquier L y R e incremente todos los números en el rango L a R en 1.

La tarea es encontrar el número mínimo de tales movimientos necesarios para ordenar la array en orden no decreciente.

Ejemplos:  

Input : arr[] = {1, 2, 3, 4}
Output : 0
The array is already sorted

Input : arr[] = {3, 2, 1}
Output : 2
Step 1: L=1 and R=2 (0-based)
Step 2: L=2 and R=2
Resultant array [3, 3, 3]
 

Considere una array ordenada, incrementar todos los elementos de la array aún daría como resultado una array ordenada.
Entonces, la idea es recorrer los elementos de la array desde la derecha, comenzando desde el último índice y siguiendo el rastro del elemento mínimo. Si en algún momento, se encuentra que el orden del elemento está aumentando, calcule el número de movimientos restando el elemento mínimo a la derecha del elemento actual.

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

// C++ program to find minimum range
// increments to sort an array
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum range
// increments to sort an array
int minMovesToSort(int arr[], int n)
{
    int moves = 0;
 
    int i, mn = arr[n - 1];
 
    for (i = n - 2; i >= 0; i--) {
 
        // If current element is found greater than
        // last element
        // Increment all terms in
        // range i+1 to n-1
        if (arr[i] > mn)
            moves += arr[i] - mn;
 
        mn = arr[i]; // Minimum in range i to n-1
    }
 
    return moves;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 5, 2, 8, 4 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << minMovesToSort(arr, n);
 
    return 0;
}

// Java program to find minimum range
// increments to sort an array
 
 
import java.io.*;
 
class GFG {
 
// Function to find minimum range
// increments to sort an array
static int minMovesToSort(int arr[], int n)
{
    int moves = 0;
 
    int i, mn = arr[n - 1];
 
    for (i = n - 2; i >= 0; i--) {
 
        // If current element is found greater than
        // last element
        // Increment all terms in
        // range i+1 to n-1
        if (arr[i] > mn)
            moves += arr[i] - mn;
 
        mn = arr[i]; // Minimum in range i to n-1
    }
 
    return moves;
}
 
// Driver Code
 
 
    public static void main (String[] args) {
        int arr[] = { 3, 5, 2, 8, 4 };
 
    int n = arr.length;
 
    System.out.println( minMovesToSort(arr, n));
    }
}
// This code is contributed by anuj_67..

# Python3 program to find minimum range
# increments to sort an array
 
# Function to find minimum range
# increments to sort an array
def minMovesToSort(arr, n) :
 
    moves = 0
 
    mn = arr[n - 1]
     
    for i in range(n - 1, -1, -1) :
 
        # If current element is found
        # greater than last element
        # Increment all terms in
        # range i+1 to n-1
        if (arr[i] > mn) :
            moves += arr[i] - mn
 
        mn = arr[i] # Minimum in range i to n-1
     
    return moves
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 3, 5, 2, 8, 4 ]
 
    n = len(arr)
 
    print(minMovesToSort(arr, n))
 
# This code is contributed by Ryuga

// C# program to find minimum range
// increments to sort an array
using System;
 
class GFG
{
// Function to find minimum range
// increments to sort an array
static int minMovesToSort(int []arr,
                          int n)
{
    int moves = 0;
 
    int i, mn = arr[n - 1];
 
    for (i = n - 2; i >= 0; i--)
    {
 
        // If current element is found
        // greater than last element
        // Increment all terms in
        // range i+1 to n-1
        if (arr[i] > mn)
            moves += arr[i] - mn;
 
        mn = arr[i]; // Minimum in range
                     // i to n-1
    }
    return moves;
}
 
// Driver Code
static public void Main ()
{
    int []arr = { 3, 5, 2, 8, 4 };
    int n = arr.Length;
     
    Console.WriteLine(minMovesToSort(arr, n));
}
}
 
// This code is contributed by ajit

<?php
// PHP program to find minimum range
// increments to sort an array
 
// Function to find minimum range
// increments to sort an array
function minMovesToSort($arr, $n)
{
    $moves = 0;
 
    $mn = $arr[$n - 1];
 
    for ($i = $n - 2; $i >= 0; $i--)
    {
 
        // If current element is found
        // greater than last element
        // Increment all terms in
        // range i+1 to n-1
        if ($arr[$i] > $mn)
            $moves += $arr[$i] - $mn;
 
        $mn = $arr[$i]; // Minimum in range i to n-1
    }
 
    return $moves;
}
 
// Driver Code
$arr = array(3, 5, 2, 8, 4 );
 
$n = sizeof($arr);
 
echo minMovesToSort($arr, $n);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
// Javascript program to find minimum range
// increments to sort an array
 
// Function to find minimum range
// increments to sort an array
function minMovesToSort(arr, n)
{
    var moves = 0;
    var i, mn = arr[n - 1];
 
    for(i = n - 2; i >= 0; i--)
    {
         
        // If current element is found greater
        // than last element
        // Increment all terms in
        // range i+1 to n-1
        if (arr[i] > mn)
            moves += arr[i] - mn;
             
        // Minimum in range i to n-1
        mn = arr[i];
    }
    return moves;
}
 
// Driver Code
var arr = [ 3, 5, 2, 8, 4 ];
var n = arr.length;
 
document.write(minMovesToSort(arr, n));
 
// This code is contributed by aashish1995
 
</script>

7

Complejidad de tiempo: O(N)