Maximize the sum of array

December 30, 2021

Maximize the sum of array

In maximize the sum of array problem we have to rearrange the array elements in such a way the the sum of array elements multiplied by their position is maximum. The problem is easy and can be solved with greedy technique. In this article we will provide C++ solution with an explanation.

Maximize the sum of array Problem Desciption

Maximize the sum of array Problem Description

Given an array of n integers. Rearrange the array elements such that sum of elements multiplied by their position index is maximum. Output the resultant sum.

Input

  • First Line contains a single integer – the size of the array.
  • Second line contains n integers the array elements.

Output

  • The maximum sum.

Problem Solution

The problem can be solved using greedy technique. Steps required are –

  • Sort the array in increasing order as we should multiply maximum index value with maximum array value and minimum index value with minimum if the array.
  • Iterate over the array elements.
  • Compute the required sum ie index * arr[i].

Time Complexity – O(n)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, sum = 0;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    sort(arr, arr + n);
    for (int i = 0; i < n; i++)
        sum += (i * arr[i]);

    cout << sum << endl;
    return 0;
}

Output

5
3 5 1 4 2
40