Suma máxima posible al hacer que la array dada no sea decreciente

Dada una array arr[], la tarea es obtener una array no decreciente con la suma máxima de la array dada al disminuir repetidamente los elementos de la array en 1.

Explicación:

Entrada: arr[] = {1, 5, 2, 3, 4}
Salida: 12
Explicación: Modifique la array dada a {1, 2, 2, 3, 4} reduciendo 5 a 2 para obtener la suma máxima posible de una array no decreciente.

Entrada: arr[] = {1, 2, 5, 9, -3}
Salida: -15

Enfoque: siga los pasos a continuación para resolver el problema:  

• Atraviesa la array en sentido inverso.
• Compare cada par de elementos adyacentes para verificar si la array no es decreciente o no , es decir, verifique si a[i – 1] ≤ a[i].
• Si se encuentra que es falso, asigne a[i – 1] = a[i] .
• Después de completar los pasos anteriores, imprima la suma de la array modificada.

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

// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
int maximumSum(vector<int> a,
               int n)
{
  //Traverse the array in
  // reverse
  for (int i = n - 1; i >= 0; i--)
  {
    //If a[i] is decreasing
    if (!(a[i - 1] <= a[i]))
      a[i - 1] = a[i];
  }
 
  int sum = 0;
 
  for(int i : a) sum += i;
 
  //Return sum of the array
  return sum;
}
 
//Driver code
int main()
{
  //Given array arr[]
  vector<int> arr = {1, 5, 2, 3, 4};
  int N = arr.size();
 
  cout << (maximumSum(arr, N));
}
 
// This code is contributed by Mohit Kumar 29

// Java program for the
// above approach
import java.util.*;
class GFG{
static int maximumSum(int[] a,
                      int n)
{
  //Traverse the array in
  // reverse
  for (int i = n - 1; i > 0; i--)
  {
    //If a[i] is decreasing
    if (!(a[i - 1] <= a[i]))
      a[i - 1] = a[i];
  }
 
  int sum = 0;
 
  for(int i : a) sum += i;
 
  //Return sum of the array
  return sum;
}
 
//Driver code
public static void main(String[] args)
{
  //Given array arr[]
  int[] arr = {1, 5, 2, 3, 4};
   
  int N = arr.length;
  System.out.print(maximumSum(arr, N));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the
# above approach
 
def maximumSum(a, n):
     
    # Traverse the array in reverse
    for i in range(n-1, 0, -1):
         
        # If a[i] is decreasing
        if not a[i-1] <= a[i]:
            a[i-1] = a[i]
               
    # Return sum of the array
    return sum(a)
 
# Driver Code
if __name__ == '__main__':
     
    arr = [1, 5, 2, 3, 4]
    N = len(arr)
     
    print(maximumSum(arr, N))

// C# program for the
// above approach
using System;
 
class GFG{
     
static int maximumSum(int[] a, int n)
{
     
    // Traverse the array in
    // reverse
    for(int i = n - 1; i > 0; i--)
    {
         
        // If a[i] is decreasing
        if (!(a[i - 1] <= a[i]))
            a[i - 1] = a[i];
    }
 
    int sum = 0;
 
    foreach(int i in a) sum += i;
 
    // Return sum of the array
    return sum;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given array []arr
    int[] arr = { 1, 5, 2, 3, 4 };
 
    int N = arr.Length;
     
    Console.Write(maximumSum(arr, N));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program for the
// above approach
 
function maximumSum(a,n)
{
    //Traverse the array in
  // reverse
  for (let i = n - 1; i > 0; i--)
  {
    //If a[i] is decreasing
    if (!(a[i - 1] <= a[i]))
      a[i - 1] = a[i];
  }
  
  let sum = 0;
  
  for(let i=0;i< a.length;i++) sum += a[i];
  
  //Return sum of the array
  return sum;
}
 
//Driver code
let arr=[1, 5, 2, 3, 4];
let N = arr.length;
document.write(maximumSum(arr, N));
 
// This code is contributed by patel2127
 
</script>

12

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