Maximize the sum of array[i]*i

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.

1. Sort the array arr[] = {2,10,13}
2. Count the sum of arr[i]* i. temp_sum = [2* 0 + 10 * 1 + 13 * 2] = 36.
3. Compare the temp sum with the maxsum and change the maxsum accordingly.
4. change the array elements for the next permutation.
5. 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 }.

1. Sort the array in assending order arr[]= {0,1,3,5,6}
2. 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)

Question