Rearrange an array to maximize i*arr, using C++

In this article, we will discuss the problem of rearranging a given array of n numbers. Basically, we have to select elements from an array. To select each element, we get some points which will be evaluated by the value of the current element * the number of elements selected before the current element. You should select elements to get the highest score. For example -

Input : arr[ ] = { 3, 1, 5, 6, 3 }

If we select the elements in the way it is given, our points will be
   = 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
   = 41
To maximize the points we have to select the elements in order { 1, 3, 3, 5, 6 }
   = 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
   = 48(maximum)

Output : 48

Input : arr[ ] = { 2, 4, 7, 1, 8 }
Output : 63

Methods to find solutions

Looking at this example, we get to get the maximum point, we need to select the elements from small to large. The solution is found by,

• sorting the given array in ascending order.
• Start selecting elements from index 0 to the end.
• Calculate the score obtained by selecting each element.

Example

#include 
#include 
using namespace std;

int main () {
   int arr[] = { 2, 4, 7, 1, 8 };
   int n = sizeof (arr) / sizeof (arr[0]);
   // sorting the array
   sort (arr, arr + n);

   int points = 0;
   // traverse the array and calculate the points
   for (int i = 0; i < n; i++) {
      points += arr[i] * i;
   }
   cout << "Maximum points: " << points;
   return 0;
}

Output

Maximum points: 63

The above code description

This C code is easy to understand. First we sort the array and then use a for loop to iterate through the array and calculate the score obtained by selecting each element from beginning to end.

Conclusion

In this article, we discussed the problem of selecting elements in an array to obtain the maximum point, where the point is calculated by i * arr[i]. We adopt a greedy approach to solve this problem and obtain the maximum score. Also discussing C code to do the same, we can write this code in any other language like C, java, Python etc. Hope this article is helpful to you.

The above is the detailed content of Rearrange an array to maximize i*arr, using C++. For more information, please follow other related articles on the PHP Chinese website!