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

What is the best sorting algorithm for the above case?

Merge Sort
Bubble sort
Quick Sort
Insertion Sort
The worst case complexity of merge sort is O(n logn), which better than others