Maximizar la suma de los elementos del Array elegidos con valor como máximo M

Dada una array arr[] de N números positivos y un entero M . La tarea es maximizar el valor de M agregando elementos de array cuando arr[i] ≤ M . 

Nota: cualquier elemento de array se puede agregar como máximo una vez.

Ejemplos: 

Entrada: arr[] = {3, 9, 19, 5, 21}, M = 10
Salida: 67
Explicación: una forma de obtener el valor es
M > 3; 3 se suma a M y se convierte en 10+3 = 13
M > 9; 9 se suma a M y se convierte en 13+9 = 22
M > 19; 19 se suma a M y se convierte en 22+19 = 41
M > 5; 5 se suma a M y se convierte en 41+5 = 46
M > 21; 21 se suma a M y se convierte en 46+21 = 67
Por lo tanto, M = 67 al final.

Entrada: arr[] = {2, 13, 4, 19}, M = 6
Salida: 12
Explicación: una forma de obtener el valor es
M > 4; 4 se suma a M y se convierte en 6+4 = 10
M > 2; 2 se suma a M y se convierte en 10+2 = 12
Ningún otro valor en la array es menor o igual a M.
Por lo tanto, M es 12 al final.

Enfoque: La solución se basa en el concepto de clasificación . Siga los pasos que se mencionan a continuación:

• Primero, ordene la array en orden creciente.
• Para cada índice i , de 0 a N-1 , haga lo siguiente:
  • Si M ≥ arr[i] , agregue arr[i] con M .
  • Si M< arr[i] , detener la iteración.
• Devuelve el valor final de M como respuesta.

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

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// the maximum value of M
// that can be obtained
int IsArrayHungry(int M, vector<int>& arr)
{
    // Sort the array in increasing order.
    sort(arr.begin(), arr.end());
    long long sum = M;
    int N = arr.size();
 
    for (int i = 0; i < N; i++) {
        if (sum >= arr[i])
            sum += arr[i];
        else
            break;
    }
    return sum;
}
 
// Driver code
int main()
{
    vector<int> arr{ 3, 9, 19, 5, 21 };
    int M = 10;
    int res = IsArrayHungry(M, arr);
    cout << res;
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG
{
 
  // Function to calculate
  // the maximum value of M
  // that can be obtained
  static int IsArrayHungry(int M, int arr[ ])
  {
 
    // Sort the array in increasing order.
    Arrays.sort(arr);
    int sum = M;
    int N = arr.length;
 
    for (int i = 0; i < N; i++) {
      if (sum >= arr[i])
        sum += arr[i];
      else
        break;
    }
    return sum;
  }
 
  // Driver code
  public static void main (String[] args)
  {
    int arr[ ] = { 3, 9, 19, 5, 21 };
    int M = 10;
    int res = IsArrayHungry(M, arr);
    System.out.print(res);
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python 3 code to implement the approach
 
# Function to calculate
# the maximum value of M
# that can be obtained
def IsArrayHungry(M,  arr):
 
    # Sort the array in increasing order.
    arr.sort()
    sum = M
    N = len(arr)
 
    for i in range(N):
        if (sum >= arr[i]):
            sum += arr[i]
 
        else:
            break
 
    return sum
 
# Driver code
if __name__ == "__main__":
 
    arr = [3, 9, 19, 5, 21]
    M = 10
    res = IsArrayHungry(M, arr)
    print(res)
 
    # This code is contributed by ukasp.

// C# code to implement above approach
using System;
class GFG
{
 
  // Function to calculate
  // the maximum value of M
  // that can be obtained
  static int IsArrayHungry(int M, int []arr)
  {
 
    // Sort the array in increasing order.
    Array.Sort(arr);
    int sum = M;
    int N = arr.Length;
 
    for (int i = 0; i < N; i++) {
      if (sum >= arr[i])
        sum += arr[i];
      else
        break;
    }
    return sum;
  }
 
  // Driver Code:
  public static void Main()
  {
    int []arr = { 3, 9, 19, 5, 21 };
    int M = 10;
    int res = IsArrayHungry(M, arr);
    Console.WriteLine(res);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
        // JavaScript code for the above approach
 
        // Function to calculate
        // the maximum value of M
        // that can be obtained
        function IsArrayHungry(M, arr)
        {
         
            // Sort the array in increasing order.
            arr.sort(function (a, b) { return a - b })
            let sum = M;
            let N = arr.length;
 
            for (let i = 0; i < N; i++) {
                if (sum >= arr[i])
                    sum += arr[i];
                else
                    break;
            }
            return sum;
        }
 
        // Driver code
        let arr = [3, 9, 19, 5, 21];
        let M = 10;
        let res = IsArrayHungry(M, arr);
        document.write(res);
 
  // This code is contributed by Potta Lokesh
    </script>

67

Complejidad de tiempo: O(N * logN)
Espacio auxiliar: O(1), ya que no se ha agregado ningún espacio adicional.