Valor máximo posible de los elementos de la array que se pueden crear en función de las condiciones de capacidad dadas

Dadas dos arrays arr[] y cap[], ambas formadas por N enteros positivos, de modo que el i ^-ésimo elemento cap[i] denota la capacidad de arr[i] , la tarea es encontrar el valor máximo posible de los elementos de la array que se pueden hecho de tal manera que se permite disminuir un elemento de array arr[i] por algún valor arbitrario e incrementar cualquiera de sus elementos adyacentes por el mismo valor si el valor final del elemento adyacente no excede su capacidad correspondiente.

Ejemplos:

Entrada: arr[] = {2, 3}, cap[] = {5, 6}
Salida: 5
Explicación:
Las siguientes operaciones se realizan para maximizar el valor de cualquier elemento en arr[]:
Operación 1: Disminuir arr[0] por 2 y aumente arr[1] en 2. Ahora arr[] = {0, 5}.
Por lo tanto, el elemento máximo en arr[] es 5.

Entrada: arr[] = {1, 2, 1}, cap[] = {2, 3, 2}
Salida: 3

Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso , que se basa en la observación de que después de realizar cualquier número de operaciones, el valor máximo no puede exceder la capacidad máxima en cap[]. Por lo tanto, la respuesta será min ( suma de todos los elementos de la array , capacidad máxima en cap[]) .

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 maximum element
// after shifting operations in arr[]
int maxShiftArrayValue(int arr[], int cap[],
                       int N)
{
    // Stores the sum of array element
    int sumVals = 0;
    for (int i = 0; i < N; i++) {
        sumVals += arr[i];
    }
 
    // Stores the maximum element in cap[]
    int maxCapacity = 0;
 
    // Iterate to find maximum element
    for (int i = 0; i < N; i++) {
        maxCapacity = max(cap[i], maxCapacity);
    }
 
    // Return the resultant maximum value
    return min(maxCapacity, sumVals);
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 3 };
    int cap[] = { 5, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxShiftArrayValue(arr, cap, N);
 
    return 0;
}

// Java program for the above approach
class GFG
{
   
    // Function to find the maximum element
    // after shifting operations in arr[]
    public static int maxShiftArrayValue(int arr[], int cap[], int N)
    {
       
        // Stores the sum of array element
        int sumVals = 0;
        for (int i = 0; i < N; i++) {
            sumVals += arr[i];
        }
 
        // Stores the maximum element in cap[]
        int maxCapacity = 0;
 
        // Iterate to find maximum element
        for (int i = 0; i < N; i++) {
            maxCapacity = Math.max(cap[i], maxCapacity);
        }
 
        // Return the resultant maximum value
        return Math.min(maxCapacity, sumVals);
    }
 
    // Driver Code
    public static void main(String args[]) {
        int arr[] = { 2, 3 };
        int cap[] = { 5, 6 };
        int N = arr.length;
 
        System.out.println(maxShiftArrayValue(arr, cap, N));
    }
}
 
// This code is contributed by gfgking.

# Python 3 program for the above approach
 
# Function to find the maximum element
# after shifting operations in arr[]
def maxShiftArrayValue(arr, cap, N):
   
    # Stores the sum of array element
    sumVals = 0
    for i in range(N):
        sumVals += arr[i]
 
    # Stores the maximum element in cap[]
    maxCapacity = 0
 
    # Iterate to find maximum element
    for i in range(N):
        maxCapacity = max(cap[i], maxCapacity)
 
    # Return the resultant maximum value
    return min(maxCapacity, sumVals)
 
# Driver Code
if __name__ == '__main__':
    arr  = [2, 3]
    cap  = [5, 6]
    N = len(arr)
    print(maxShiftArrayValue(arr, cap, N))
     
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
class GFG {
 
    // Function to find the maximum element
    // after shifting operations in arr[]
    public static int maxShiftArrayValue(int[] arr,
                                         int[] cap, int N)
    {
 
        // Stores the sum of array element
        int sumVals = 0;
        for (int i = 0; i < N; i++) {
            sumVals += arr[i];
        }
 
        // Stores the maximum element in cap[]
        int maxCapacity = 0;
 
        // Iterate to find maximum element
        for (int i = 0; i < N; i++) {
            maxCapacity = Math.Max(cap[i], maxCapacity);
        }
 
        // Return the resultant maximum value
        return Math.Min(maxCapacity, sumVals);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { 2, 3 };
        int[] cap = { 5, 6 };
        int N = arr.Length;
 
        Console.WriteLine(maxShiftArrayValue(arr, cap, N));
    }
}
 
// This code is contributed by ukasp.

<script>
       // JavaScript Program to implement
       // the above approach
 
       // Function to find the maximum element
       // after shifting operations in arr[]
       function maxShiftArrayValue(arr, cap, N)
       {
        
           // Stores the sum of array element
           let sumVals = 0;
           for (let i = 0; i < N; i++) {
               sumVals += arr[i];
           }
 
           // Stores the maximum element in cap[]
           let maxCapacity = 0;
 
           // Iterate to find maximum element
           for (let i = 0; i < N; i++) {
               maxCapacity = Math.max(cap[i], maxCapacity);
           }
 
           // Return the resultant maximum value
           return Math.min(maxCapacity, sumVals);
       }
 
       // Driver Code
       let arr = [2, 3];
       let cap = [5, 6];
       let N = arr.length
 
       document.write(maxShiftArrayValue(arr, cap, N));
 
    // This code is contributed by Potta Lokesh
   </script>

5

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