Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 20 minutes | Coding time: 5 minutes

Given an array of N integer, we have to maximize the sum of arr[i] * i, where i is the index of the element (i = 0, 1, 2, ..., N). We can rearrange the position of the integer in the array to maximize the sum.

We show two approaches to solve this:

**Brute force**O(N * N!)**Greedy algorithm**O(N log N)

**Example**:

Consider the following array:

arr[] = {2,5,3,4,0}

In this arrangement, the sum of products will be:

```
2 * 0 + 5 * 1 + 3 * 2 + 4 * 3 + 0 * 5
= 0 + 5 + 6 + 12 + 0
= 23
```

To maximize the sum we have to arrange the array as [0,2,3,4,5]

So the sum will be

```
0 * (0) + 2 * (1) + 3 * (2) + 4 * (3) + 5 * (4)
= 0 + 2 + 6 + 12 + 20
= 40
```

So 40 is the maximum for the given array.

## Naive Approach

A simple solution is to generate all permutations of the given array. For every permutation, compute the value of Ξ£arr[i]*i and finally return the maximum value.

### Example

arr[] = {10,2,13}

So to get all the permutation for the given array we will sort the array.

- Sort the array arr[] = {2,10,13}
- Count the sum of arr[i]* i. temp_sum = [2* 0 + 10 * 1 + 13 * 2] = 36.
- Compare the temp sum with the maxsum and change the maxsum accordingly.
- change the array elements for the next permutation.
- Repeat step 2.

Possible permutations are:

```
2 10 13 sum is: 36
2 13 10 sum is: 33
10 2 13 sum is: 28
10 13 2 sum is: 17
13 2 10 sum is: 22
13 10 2 sum is: 14
```

Maximum Sum is: 36

## Implementation (Brute force)

```
#include <bits/stdc++.h>
using namespace std;
int max_sum(int a[], int n)
{
sort(a, a + n);
int sum = INT_MIN;
do {
int temp_sum = 0;
for (int i = 0; i < n; i++) {
temp_sum += a[i]*i;
sum = max(temp_sum,sum);
}
} while (next_permutation(a, a + n));
return sum;
}
int main()
{
int n = 5;
int a[] = {10,2,13,40,5 };
cout <<"The max sum is: " << max_sum(a, n);
return 0;
}
```

Output

```
The max sum is: 224
```

For the above code time complexity will be around **Ξ(N*N!)**

## Greedy Approach

So, with a greedy approach, we will try to pair the largest value with the maximum index and the smallest value should be paired with a minimum index. So we multiply the minimum value of i with a minimum value of arr[i].

So, sort the given array in increasing order and compute the sum of ari]*i, where i = 0 to n-1.

### Example

arr[] = { 3, 5, 6, 1, 0 }.

- Sort the array in assending order arr[]= {0,1,3,5,6}
- Iterate over the array and calculate the sum for arr[i]* i.

sum = [0* 0+1* 1+3* 2+5* 3+6* 4] = 46

The maximum sum is 46.

### Implementation (Greedy algorithm)

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N = 5;
int arr[] = { 3, 5, 6, 1, 0 };
sort(arr, arr + N); // sort in assesding order
int sum = 0;
for (int i = 0; i < N; i++)
sum += (arr[i]*i);
cout << "Maximun sum is: " << sum << endl;
return 0;
}
```

Output:

```
Maximun sum is: 46
```

## Complexity

- Worst case time complexity:
**Ξ(N log N)**