Maximizar la suma de arr[i]*i

Dada una array de N enteros. Se le permite reorganizar los elementos de la array. La tarea es encontrar el valor máximo de Σarr[i]*i, donde i = 0, 1, 2,…., n – 1.

Ejemplos:  

Input : N = 4, arr[] = { 3, 5, 6, 1 }
Output : 31
If we arrange arr[] as { 1, 3, 5, 6 }. 
Sum of arr[i]*i is 1*0 + 3*1 + 5*2 + 6*3 
= 31, which is maximum

Input : N = 2, arr[] = { 19, 20 }
Output : 20

Una solución simple es generar todas las permutaciones de un arreglo dado . Para cada permutación, calcule el valor de Σarr[i]*i y finalmente devuelva el valor máximo.

Una solución eficiente se basa en el hecho de que el valor más grande debe escalarse al máximo y el valor más pequeño debe escalarse al mínimo. Entonces multiplicamos el valor mínimo de i con el valor mínimo de arr[i]. Entonces, ordene la array dada en orden creciente y calcule la suma de arr[i]*i, donde i = 0 a n-1.

A continuación se muestra la implementación de este enfoque:  

// CPP program to find the maximum value
// of i*arr[i]
#include<bits/stdc++.h>
using namespace std;
 
int maxSum(int arr[], int n)
{ 
  // Sort the array
  sort(arr, arr + n);
 
  // Finding the sum of arr[i]*i
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += (arr[i]*i);
 
  return sum;
}
 
// Driven Program
int main()
{
  int arr[] = { 3, 5, 6, 1 };
  int n = sizeof(arr)/sizeof(arr[0]);
 
  cout << maxSum(arr, n) << endl;
  return 0;
}

// Java program to find the
// maximum value of i*arr[i]
import java.util.*;
 
class GFG {
 
    static int maxSum(int arr[], int n)
    {   
    // Sort the array
    Arrays.sort(arr);
 
    // Finding the sum of arr[i]*i
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += (arr[i] * i);
 
    return sum;
    }
 
    // Driven Program
    public static void main(String[] args)
    {
    int arr[] = { 3, 5, 6, 1 };
    int n = arr.length;
 
    System.out.println(maxSum(arr, n));
 
    }
}
// This code is contributed by Prerna Saini

# Python program to find the
# maximum value of i*arr[i]
def maxSum(arr,n):
 
    #  Sort the array
    arr.sort()
 
    # Finding the sum of
    # arr[i]*i
    sum = 0
    for i in range(n):
        sum += arr[i] * i
         
    return sum
 
# Driver Program
arr = [3,5,6,1]
n = len(arr)
print(maxSum(arr,n))
 
# This code is contributed
# by Shrikant13

// C# program to find the
// maximum value of i*arr[i]
using System;
 
class GFG {
     
    // Function to find the
    // maximum value of i*arr[i]
    static int maxSum(int[] arr, int n)
    {
         
        // Sort the array
        Array.Sort(arr);
     
        // Finding the sum of arr[i]*i
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += (arr[i] * i);
     
        return sum;
    }
 
    // Driver code
    static public void Main()
    {
        int[] arr = {3, 5, 6, 1};
        int n = arr.Length;
     
        Console.WriteLine(maxSum(arr, n));
 
    }
}
 
// This code is contributed by Ajit.

<?php
// PHP program to find the
// maximum value of i*arr[i]
 
// function returns the
// maximum value of i*arr[i]
function maxSum($arr, $n)
{
    // Sort the array
    sort($arr);
     
    // Finding the sum
    // of arr[i]*i
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += ($arr[$i] * $i);
     
    return $sum;
}
 
// Driver Code
$arr = array( 3, 5, 6, 1 );
$n = count($arr);
 
echo maxSum($arr, $n);
 
// This code is contributed by anuj_67.
?>

<script>
// JavaScript program to find the
// maximum value of i*arr[i]
 
function maxSum(arr, n)
    {   
    // Sort the array
    arr.sort();
 
    // Finding the sum of arr[i]*i
    let sum = 0;
    for (let i = 0; i < n; i++)
        sum += (arr[i] * i);
 
    return sum;
    }
  
// Driver Code
 
    let arr = [ 3, 5, 6, 1 ];
    let n = arr.length;
 
    document.write(maxSum(arr, n));
         
</script>

31

Complejidad temporal: O(n Log n)
Espacio auxiliar: O(1)

Este artículo es una contribución de Anuj Chauhan (anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.