Elimine todas las apariciones de cualquier elemento para obtener la suma máxima de la array

Dada una array de enteros positivos, elimine todas las ocurrencias del elemento para obtener la suma máxima de la array restante.

Ejemplos: 

Entrada: arr = {1, 1, 3} 
Salida: 3 
Al quitar 1 de la array, obtenemos {3}. el valor total es 3

Entrada: arr = {1, 1, 3, 3, 2, 2, 1, 1, 1} 
Salida: 11 
Al eliminar 2 de la array, obtenemos {1, 1, 3, 3, 1, 1, 1} . El valor total es 11. 

La solución de fuerza bruta es primero encontrar la suma de una array, luego de eso, encontrar todas las frecuencias de los elementos en la array. Encuentre el valor aportado por ellos a la suma del arreglo. Seleccione el valor mínimo entre ellos. Para obtener la suma máxima de la array después de eliminarla, es igual la diferencia del valor total de la suma y el valor mínimo aportado por el valor frecuente total del elemento individual.
Complejidad temporal: O(n ² )

Un mejor enfoque Primero encontramos la suma total de la array y luego ordenamos la array, contamos las frecuencias individuales mientras recorremos la array y obtenemos el valor máximo. Después de ordenar, podemos usar las frecuencias de todos los elementos en tiempo O(n). 
La complejidad temporal de este enfoque es O(n Log n)

Un enfoque eficiente es usar hash para contar las frecuencias de los elementos mientras se recorre la array. Encuentre el valor mínimo usando las frecuencias almacenadas en la array 

#include <bits/stdc++.h>
using namespace std;
 
int maxSumArray(int arr[], int n)
{
    // Find total sum and frequencies of elements
    int sum = 0;
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        mp[arr[i]]++;
    }
 
    // Find minimum value to be subtracted.
    int minimum = INT_MAX;
    for (auto x : mp)
        minimum = min(minimum, x.second * x.first);
 
    // Find maximum sum after removal
    return (sum - minimum);
}
 
// Drivers code
int main()
{
    int arr[] = { 1, 1, 3, 3, 2, 2, 1, 1, 1 };
    int n = sizeof(arr) / sizeof(int);
    cout << maxSumArray(arr, n);
    return 0;
}

// Java program to convert fractional decimal
// to binary number
import java.util.*;
 
class GFG
{
 
static int maxSumArray(int arr[], int n)
{
    // Find total sum and frequencies of elements
    int sum = 0;
    Map<Integer,Integer> m = new HashMap<>();
    for (int i = 0 ; i < n; i++)
    {
        sum += arr[i];
        if(m.containsKey(arr[i]))
        {
            m.put(arr[i], m.get(arr[i])+1);
        }
        else
        {
            m.put(arr[i], 1);
        }
    }
     
    // Find minimum value to be subtracted.
    int minimum = Integer.MAX_VALUE;
    for (Map.Entry<Integer,Integer> x : m.entrySet())
        minimum = Math.min(minimum, x.getValue() * x.getKey());
 
    // Find maximum sum after removal
    return (sum - minimum);
}
 
// Drivers code
public static void main(String[] args)
{
    int arr[] = { 1, 1, 3, 3, 2, 2, 1, 1, 1 };
    int n = arr.length;
    System.out.println(maxSumArray(arr, n));
}
}
 
// This code contributed by Rajput-Ji

# Python3 program to convert
# fractional decimal to binary number
from sys import maxsize
def maxSumArray(arr, n):
     
    # Find total sum and frequencies of elements
    sum1 = 0
    mp = {i:0 for i in range(4)}
    for i in range(n):
        sum1 += arr[i]
        mp[arr[i]] += 1
 
    # Find minimum value to be subtracted.
    minimum = maxsize
    for key, value in mp.items():
        if(key == 0):
            continue
        minimum = min(minimum, value * key)
 
    # Find maximum sum after removal
    return (sum1 - minimum)
 
# Driver Code
if __name__ =='__main__':
    arr = [1, 1, 3, 3, 2, 2, 1, 1, 1]
    n = len(arr)
    print(maxSumArray(arr, n))
     
# This code is contributed by
# Surendra_Gangwar

// C# program to convert fractional decimal
// to binary number
using System;
using System.Collections.Generic;
 
class GFG
{
 
static int maxSumArray(int []arr, int n)
{
    // Find total sum and frequencies of elements
    int sum = 0;
    Dictionary<int,int> m = new Dictionary<int,int>();
    for (int i = 0 ; i < n; i++)
    {
        sum += arr[i];
        if(m.ContainsKey(arr[i]))
        {
            var val = m[arr[i]];
            m.Remove(arr[i]);
            m.Add(arr[i], val + 1);
        }
        else
        {
            m.Add(arr[i], 1);
        }
    }
     
    // Find minimum value to be subtracted.
    int minimum = int.MaxValue;
    foreach(KeyValuePair<int, int> x in m)
        minimum = Math.Min(minimum, (x.Value * x.Key));
 
    // Find maximum sum after removal
    return (sum - minimum);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 1, 3, 3, 2, 2, 1, 1, 1 };
    int n = arr.Length;
    Console.WriteLine(maxSumArray(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
function maxSumArray(arr, n)
{
    // Find total sum and frequencies of elements
    var sum = 0;
    var mp = new Map();
    for (var i = 0; i < n; i++) {
        sum += arr[i];
        if(mp.has(arr[i]))
            mp.set(arr[i], mp.get(arr[i])+1)
        else   
            mp.set(arr[i], 1)
    }
 
    // Find minimum value to be subtracted.
    var minimum = 1000000000;
    mp.forEach((value, key) => {
        minimum = Math.min(minimum, value * key);
    });
 
    // Find maximum sum after removal
    return (sum - minimum);
}
 
// Drivers code
var arr = [1, 1, 3, 3, 2, 2, 1, 1, 1];
var n = arr.length;
document.write( maxSumArray(arr, n));
 
</script>

11

Complejidad temporal: O(n)