# Maximize the sum of array

## 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 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 nsum = 0;
cin >> n;
int arr[n];
for (int i = 0i < ni++)
cin >> arr[i];

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

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

### Output

`53 5 1 4 240`