Given an array of N integers, you have to select all of these integers in any order. For every integer you select, you get points equal to the value of: the selected integer * number of integers selected before the current integer. Your task is to maximize these points.
Note: You can select every integer exactly 1 time.
Examples:
Input: a = {1, 4, 2, 3, 9}
Output: 56
The optimal solution for this array would be select the numbers in the order 1, 2, 3, 4, 9 that gives points 0, 2, 6, 12, 36 respectively and giving a total maximum points of 56.Input: a = {1, 2, 2, 4, 9}
Output: 54
The optimal solution for this array would be select the numbers in the order 1, 2, 2, 4, 9 that gives points 0, 2, 4, 12, 36 respectively and giving a total maximum points of 54.
The idea is to use Greedy Approach, i.e., maximize the multiplier for the largest element. We sort the given array and start picking elements in this sorted manner, starting with the first element.
Below is the implementation of the above approach:
C++
// C++ program for the Optimal Solution#include <bits/stdc++.h> #include <iostream>using namespace std; // Function to calculate the maximum points // earned by making an optimal selection on // the given array static int findOptimalSolution(int a[], int N) { // Sorting the array sort(a, a+N); // Variable to store the total points earned int points = 0; for (int i = 0; i < N; i++) { points += a[i] * i; } return points; } // Driver codeint main() { int a[] = { 1, 4, 2, 3, 9 }; int N = sizeof(a)/sizeof(a[0]); cout<<(findOptimalSolution(a, N)); return 0;} |
Java
// Java program for the Optimal Solutionimport java.io.*;import java.util.*;class GFG { // Function to calculate the maximum points // earned by making an optimal selection on // the given array static int findOptimalSolution(int[] a, int N) { // Sorting the array Arrays.sort(a); // Variable to store the total points earned int points = 0; for (int i = 0; i < N; i++) { points += a[i] * i; } return points; } // Driver code public static void main(String args[]) { int[] a = { 1, 4, 2, 3, 9 }; int N = a.length; System.out.println(findOptimalSolution(a, N)); }} |
Python3
# Python3 program for the Optimal Solution # Function to calculate the maximum points # earned by making an optimal selection on # the given array def findOptimalSolution(a, N) : # Sorting the array a.sort() # Variable to store the total points earned points = 0 for i in range(0, N): points += a[i] * i return points if __name__ == "__main__": a = [1, 4, 2, 3, 9] N = len(a) print(findOptimalSolution(a, N)) |
C#
//C# program for the Optimal Solutionusing System;public class GFG{ // Function to calculate the maximum points // earned by making an optimal selection on // the given array static int findOptimalSolution(int[]a, int N) { // Sorting the array Array.Sort(a); // Variable to store the total points earned int points = 0; for (int i = 0; i < N; i++) { points += a[i] * i; } return points; } // Driver code static public void Main (){ int[] a = { 1, 4, 2, 3, 9 }; int N = a.Length; Console.WriteLine(findOptimalSolution(a, N)); }//This code is contributed by ajit } |
PHP
<?php// PHP program for the Optimal Solution// Function to calculate the maximum // points earned by making an optimal// selection on the given arrayfunction findOptimalSolution($a, $N){ // Sorting the array sort($a); // Variable to store the // total points earned $points = 0; for ($i = 0; $i < $N; $i++) { $points += $a[$i] * $i; } return $points;}// Driver code$a = array( 1, 4, 2, 3, 9 );$N = sizeof($a);echo (findOptimalSolution($a, $N));// This code is contributed by ajit?> |
Javascript
<script> // Javascript program for the Optimal Solution // Function to calculate the maximum points // earned by making an optimal selection on // the given array function findOptimalSolution(a, N) { // Sorting the array a.sort(function(a, b){return a - b}); // Variable to store the total points earned let points = 0; for (let i = 0; i < N; i++) { points += a[i] * i; } return points; } let a = [ 1, 4, 2, 3, 9 ]; let N = a.length; document.write(findOptimalSolution(a, N)); </script> |
56
Complexity analysis:
- Time Complexity: O(n log(n))
- Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
