Dada una array arr[] que contiene N enteros positivos, la tarea es maximizar la suma de la array cuando, después de cada operación de suma, todos los elementos restantes de la array disminuyen en 1.
Nota: El valor de un elemento de array no va por debajo de 0.
Ejemplos:
nput: arr[] = {6, 2, 4, 5}
Output: 12
Explanation: Add 6 initially to the final sum.
The final sum becomes 6 and the remaining array elements {1, 3, 4}.
Add 3 with the sum. The sum becomes 9 and the remaining elements {0, 3}
Add 3 with the sum. The sum becomes 12 and only 0 remains in the array.
Add 0 with the sum. The sum remains unchanged.
Input: arr[] = {5, 6, 4}
Output: 12
Enfoque ingenuo: encuentre el elemento máximo de la array. Agréguelo a la suma y disminuya todos los demás elementos en 1 y cambie el elemento actual a 0 para que no se repita nuevamente en el ciclo. Haz este proceso hasta que todos los elementos se conviertan en 0.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Find maximum possible sum
int maxSum(int arr[], int N)
{
// Initialize ans with 0
int ans = 0;
// loop till atleast one element is greater than 0
while (1) {
// maximum element of array
int maxValueIndex = max_element(arr, arr + N) - arr;
// breaking condition when all elements become <=0
if (arr[maxValueIndex] <= 0)
break;
// adding value to answer
ans += arr[maxValueIndex];
arr[maxValueIndex] = 0;
// Iterate array
for (int i = 0; i < N; i++) {
arr[i]--;
}
}
return ans;
}
// Driver code
int main()
{
// Given array of values
int arr[] = { 6, 2, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << maxSum(arr, N);
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
class GFG
{
// Find maximum possible sum
static int maxSum(int arr[], int N)
{
// Initialize ans with 0
int ans = 0;
// loop till atleast one element is greater than 0
while (true) {
// maximum element of array
int maxValue = Arrays.stream(arr).max().getAsInt();
;
int maxValueIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == maxValue) {
maxValueIndex = i;
break;
}
}
// breaking condition when all elements become <=0
if (arr[maxValueIndex] <= 0)
break;
// adding value to answer
ans += arr[maxValueIndex];
arr[maxValueIndex] = 0;
// Iterate array
for (int i = 0; i < N; i++) {
arr[i]--;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
// Given array of values
int arr[] = { 6, 2, 4, 5 };
int N = arr.length;
// Function call
System.out.print(maxSum(arr, N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python code to implement the above approach # Find maximum possible sum def maxSum(arr, N): # Initialize ans with 0 ans = 0 # loop till atleast one element is greater than 0 while (1): # maximum element of array maxValueIndex = arr.index(max(arr)) # breaking condition when all elements become <=0 if (arr[maxValueIndex] <= 0): break # adding value to answer ans += arr[maxValueIndex] arr[maxValueIndex] = 0 # Iterate array for i in range(0, N): arr[i] -= 1 return ans # Driver code # Given array of values arr = [6, 2, 4, 5] N = len(arr) # Function call print(maxSum(arr, N)) # This code is contributed by ninja_hattori.
C#
// C# code to implement the above approach
using System;
using System.Linq;
class GFG
{
// Find maximum possible sum
static int maxSum(int[] arr, int N)
{
// Initialize ans with 0
int ans = 0;
// loop till atleast one element is greater than 0
while (true) {
// maximum element of array
int maxValue = arr.Max();
int maxValueIndex = 0;
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == maxValue) {
maxValueIndex = i;
break;
}
}
// breaking condition when all elements become <=0
if (arr[maxValueIndex] <= 0)
break;
// adding value to answer
ans += arr[maxValueIndex];
arr[maxValueIndex] = 0;
// Iterate array
for (int i = 0; i < N; i++) {
arr[i]--;
}
}
return ans;
}
// Driver code
public static int Main()
{
// Given array of values
int[] arr = { 6, 2, 4, 5 };
int N = arr.Length;
// Function call
Console.Write(maxSum(arr, N));
return 0;
}
}
// This code is contributed by Pushpesh Raj
Javascript
<script>
// JavaScript code to implement the above approach
// Find maximum possible sum
function maxSum(arr, N)
{
// Initialize ans with 0
let ans = 0;
// loop till atleast one element is greater than 0
while (1) {
// maximum element of array
let maxValueIndex = arr.indexOf(Math.max(...arr));
// breaking condition when all elements become <=0
if (arr[maxValueIndex] <= 0)
break;
// adding value to answer
ans += arr[maxValueIndex];
arr[maxValueIndex] = 0;
// Iterate array
for (let i = 0; i < N; i++) {
arr[i]--;
}
}
return ans;
}
// Driver code
// Given array of values
let arr = [ 6, 2, 4, 5 ];
let N = arr.length;
// Function call
document.write(maxSum(arr, N));
// This code is contributed by shinjanpatra
</script>
Producción
12
Complejidad del Tiempo: O(N 2 )
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Enfoque eficiente: La solución del problema se basa en el concepto de clasificación . A medida que los valores disminuyen en cada paso, los valores más altos deben agregarse primero con la suma final. Siga los pasos que se mencionan a continuación para resolver el problema:
- Ordene la array en orden descendente .
- Ejecute un ciclo de 1 a N .
- Para cada índice i, el valor agregado a la suma final será (arr[i] – i) ya que se agregará después de la disminución del valor i .
- Como el valor de la suma no puede ser inferior a 0 , agregue max(arr[i]-i, 0) a la suma final.
- Devolver la suma final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Find maximum possible sum
int maxSum(int arr[], int N)
{
// Initialize ans with 0
int ans = 0;
// Sort array in descending order
sort(arr, arr + N, greater<int>());
// Iterate array
for (int i = 0; i < N; i++) {
// Starting value
int value = arr[i];
// Actual value when being added
int current = max(0, value - i);
// Add actual value with ans
ans = ans + current;
}
return ans;
}
// Driver code
int main()
{
// Given array of values
int arr[] = { 6, 2, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << maxSum(arr, N);
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
public class GFG
{
// Utility program to reverse an array
public static void reverse(int[] array)
{
// Length of the array
int n = array.length;
// Swaping the first half elements with last half
// elements
for (int i = 0; i < n / 2; i++) {
// Storing the first half elements temporarily
int temp = array[i];
// Assigning the first half to the last half
array[i] = array[n - i - 1];
// Assigning the last half to the first half
array[n - i - 1] = temp;
}
}
// Find maximum possible sum
static int maxSum(int[] arr, int N)
{
// Initialize ans with 0
int ans = 0;
// Sorting the array in ascending order
Arrays.sort(arr);
// Reversing the array
reverse(arr);
// Iterate array
for (int i = 0; i < N; i++) {
// Starting value
int value = arr[i];
// Actual value when being added
int current = Math.max(0, value - i);
// Add actual value with ans
ans = ans + current;
}
return ans;
}
// Driver code
public static void main(String args[])
{
// Given array of values
int[] arr = { 6, 2, 4, 5 };
int N = arr.length;
// Function call
System.out.println(maxSum(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python
# Python code to implement the above approach # Find maximum possible sum def maxSum(arr, N): # Initialize ans with 0 ans = 0 # Sort array in descending order arr.sort(reverse = True) # Iterate array for i in range(N): #Starting value value = arr[i] # Actual value when being added current = max(0, value - i) # Add actual value with ans ans = ans + current return ans # Driver code if __name__ == "__main__": # Given array of values arr = [ 6, 2, 4, 5 ] N = len(arr) # Function call print(maxSum(arr, N)) # This code is contributed by hrithikgarg03188.
C#
// C# code to implement the above approach
using System;
class GFG
{
// Find maximum possible sum
static int maxSum(int[] arr, int N)
{
// Initialize ans with 0
int ans = 0;
// Sort array in descending order
Array.Sort<int>(
arr, delegate(int m, int n) { return n - m; });
// Iterate array
for (int i = 0; i < N; i++) {
// Starting value
int value = arr[i];
// Actual value when being added
int current = Math.Max(0, value - i);
// Add actual value with ans
ans = ans + current;
}
return ans;
}
// Driver code
public static int Main()
{
// Given array of values
int[] arr = { 6, 2, 4, 5 };
int N = arr.Length;
// Function call
Console.Write(maxSum(arr, N));
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// JavaScript code for the above approach
// Find maximum possible sum
function maxSum(arr, N)
{
// Initialize ans with 0
let ans = 0;
// Sort array in descending order
arr.sort(function (a, b) { return b - a })
// Iterate array
for (let i = 0; i < N; i++) {
// Starting value
let value = arr[i];
// Actual value when being added
let current = Math.max(0, value - i);
// Add actual value with ans
ans = ans + current;
}
return ans;
}
// Driver code
// Given array of values
let arr = [6, 2, 4, 5];
let N = arr.length;
// Function call
document.write(maxSum(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción
12
Complejidad temporal: O(N log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por geekygirl2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA