Dada una array arr[] que consta de N enteros positivos, la tarea es maximizar la suma del elemento de la array de modo que el primer elemento de la array sea 1 y la diferencia entre los elementos adyacentes de la array sea como máximo 1 después de realizar la siguientes operaciones:
- Reorganizar los elementos de la array de cualquier manera.
- Reducir cualquier elemento a cualquier número que sea al menos 1 .
Ejemplos:
Entrada: arr[] = {3, 5, 1}
Salida: 6
Explicación:
Una disposición posible es {1, 2, 3} con la suma máxima posible de 6.Entrada: arr[] = {1, 2, 2, 2, 3, 4, 5}
Salida: 19
Explicación:
Un arreglo posible es {1, 2, 2, 2, 3, 4, 5} que tiene la suma máxima posible 19 .
Enfoque ingenuo: el enfoque más simple es ordenar la array dada , luego atravesar la array ordenada y reducir el elemento que no satisface la condición dada.
Complejidad de tiempo: O (N * log N), donde N es el tamaño de la array dada.
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el concepto Hashing para almacenar las frecuencias de los elementos de la array dada. Siga los pasos a continuación para resolver el problema:
- Cree una array auxiliar count[] de tamaño (N+1) para almacenar la frecuencia de arr[i] .
- Mientras almacena la frecuencia en count[] y si arr[i] es mayor que N , incremente count[N] .
- Inicialice el tamaño y ans como 0 que almacena el número entero previamente seleccionado y la suma máxima posible respectivamente.
- Recorra la array de conteo [] dada usando la variable K y haga lo siguiente:
- Iterar durante un ciclo para cada K hasta contar[K] > 0 y tamaño < K .
- Incremente el tamaño en 1 y ans en tamaño y reduzca la cuenta [K] en 1 dentro del ciclo while.
- Incremente ans con K*count[K] después de que termine el bucle while.
- Después de los pasos anteriores, imprima el valor de ans como la suma máxima posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find maximum possible
// sum after changing the array elements
// as per the given constraints
long maxSum(int a[], int n)
{
// Stores the frequency of
// elements in given array
int count[n + 1] = {0};
// Update frequency
for(int i = 0; i < n; i++)
count[min(a[i], n)]++;
// Stores the previously
// selected integer
int size = 0;
// Stores the maximum possible sum
long ans = 0;
// Traverse over array count[]
for(int k = 1; k <= n; k++)
{
// Run loop for each k
while (count[k] > 0 && size < k)
{
size++;
ans += size;
count[k]--;
}
// Update ans
ans += k * count[k];
}
// Return maximum possible sum
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 3, 5, 1 };
// Size of array
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << (maxSum(arr, n));
return 0;
}
// This code is contributed by akhilsaini
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find maximum possible
// sum after changing the array elements
// as per the given constraints
static long maxSum(int[] a)
{
// Length of given array
int n = a.length;
// Stores the frequency of
// elements in given array
int[] count = new int[n + 1];
// Update frequency
for (int x : a)
count[Math.min(x, n)]++;
// stores the previously
// selected integer
int size = 0;
// Stores the maximum possible sum
long ans = 0;
// Traverse over array count[]
for (int k = 1; k <= n; k++) {
// Run loop for each k
while (count[k] > 0 && size < k) {
size++;
ans += size;
count[k]--;
}
// Update ans
ans += k * count[k];
}
// Return maximum possible sum
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 3, 5, 1 };
// Function Call
System.out.println(maxSum(arr));
}
}
Python3
# Python3 program for the above approach # Function to find maximum possible # sum after changing the array elements # as per the given constraints def maxSum(a, n): # Stores the frequency of # elements in given array count = [0] * (n + 1) # Update frequency for i in range(0, n): count[min(a[i], n)] += 1 # stores the previously # selected integer size = 0 # Stores the maximum possible sum ans = 0 # Traverse over array count[] for k in range(1, n + 1): # Run loop for each k while (count[k] > 0 and size < k): size += 1 ans += size count[k] -= 1 # Update ans ans += k * count[k] # Return maximum possible sum return ans # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 3, 5, 1 ] # Size of array n = len(arr) # Function Call print(maxSum(arr, n)) # This code is contributed by akhilsaini
C#
// C# program for the above approach
using System;
class GFG{
// Function to find maximum possible
// sum after changing the array elements
// as per the given constraints
static long maxSum(int[] a)
{
// Length of given array
int n = a.Length;
// Stores the frequency of
// elements in given array
int[] count = new int[n + 1];
// Update frequency
for(int i = 0; i < n; i++)
count[Math.Min(a[i], n)]++;
// stores the previously
// selected integer
int size = 0;
// Stores the maximum possible sum
long ans = 0;
// Traverse over array count[]
for(int k = 1; k <= n; k++)
{
// Run loop for each k
while (count[k] > 0 && size < k)
{
size++;
ans += size;
count[k]--;
}
// Update ans
ans += k * count[k];
}
// Return maximum possible sum
return ans;
}
// Driver Code
public static void Main()
{
// Given array arr[]
int[] arr = { 3, 5, 1 };
// Function call
Console.Write(maxSum(arr));
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program for the above approach
// Function to find maximum possible
// sum after changing the array elements
// as per the given constraints
function maxSum( a, n)
{
// Stores the frequency of
// elements in given array
var count = Array(n+1).fill(0);
// Update frequency
for(var i = 0; i < n; i++)
count[Math.min(a[i], n)]++;
// Stores the previously
// selected integer
var size = 0;
// Stores the maximum possible sum
var ans = 0;
// Traverse over array count[]
for(var k = 1; k <= n; k++)
{
// Run loop for each k
while (count[k] > 0 && size < k)
{
size++;
ans += size;
count[k]--;
}
// Update ans
ans += k * count[k];
}
// Return maximum possible sum
return ans;
}
// Driver Code
// Given array arr[]
var arr = [ 3, 5, 1 ];
// Size of array
var n = arr.length;
// Function Call
document.write(maxSum(arr, n));
// This code is contributed by noob2000.
</script>
Producción:
6
Complejidad de tiempo: O(N), donde N es el tamaño de la array dada. Como estamos usando un ciclo para atravesar la array N veces.
Espacio auxiliar: O(N) , ya que estamos usando un espacio adicional para contar la array.