Максимально возможная сумма, если сделать данный массив неубывающим

Опубликовано: 1 Декабря, 2021

Для данного массива arr [] задача состоит в том, чтобы получить неубывающий массив с максимальной суммой из данного массива путем многократного уменьшения элементов массива на 1.

Объяснение:

Input: arr[] = {1, 5, 2, 3, 4}
Output: 12
Explanation: Modify the given array to {1, 2, 2, 3, 4} by reducing 5 to 2 to obtain maximum sum possible from a non-decreasing array.
Input: arr[] = {1, 2, 5, 9, -3}
Output: -15

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: выполните следующие действия, чтобы решить проблему:

Пройдите по массиву в обратном порядке.
Сравните каждую пару соседних элементов, чтобы проверить, не убывает ли массив, т.е. проверьте, является ли a [i - 1] ≤ a [i].
Если обнаружено, что это ложь, присвойте a [i - 1] = a [i] .
После выполнения вышеуказанных шагов p [rin t сумма измененного массива.

Ниже представлена реализация описанного выше подхода:

C ++

 // 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
  sum; return
 }
 //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
  sum; return
 }
 //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

 # 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
    sum return (a)
 # Driver Code
 if __name__ = = '__main__' :
    
    arr = [ 1 , 5 , 2 , 3 , 4 ]
    N = len (arr)
    
    print (maximumSum(arr, N)) 

C #

 // 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
    sum; return
 }
 // 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

Выход:

Сложность времени: O (N)
Вспомогательное пространство: O (1)

Technical Scripter

Максимально возможная сумма, если сделать данный массив неубывающим

C ++

Ява

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ