Find Maximum Value of Sum using Array Rotations in C++

In this problem, we are given an array arr[] consisting of n elements. We need to Find maximum value of Sum( i*arr[i]) with only rotations on a given array allowed. For find the maximum sum of (i*arr[i]), we can perform any number of rotations.

Let’s take an example to understand the problem,

Input

arr[] = {4, 1, 3, 7, 2}

Output

43

Explanation

We will rotate the array once to get the maximum value, After rotation array will be {2, 4, 1, 3, 7}

Sum = 0*2 + 1*4 + 2*1 + 3*3 + 4*7 = 0 + 4 + 2 + 9 + 28 = 43

Solution approach

A simple solution to the problem is by rotating the array n times. After each rotation, we will find the sum(i*arr[i]) and return the maximum of all the values. This is great but the time complexity is of the order O(n2). A more efficient solution to the problem is by finding the value of sum(i*arr[i]) without rotation using the formula.

Let’s derive the formula mathematically,

Let the sum after k rotation is equal to sum(k).
sum(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] => eq 1

Now , we will rotate the values after which the sum will become,

sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => eq 2 Subtracting eq2 - eq 1
sum(1) - sum(0) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] - 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1]
sum(1) - sum(0) = arr[0] + arr[1] + … arr[n-2 ] - (n - 1)*arr[n-1]

Similarly for sum(2) - sum(1),

sum(2) - sum(1) = arr[0] + arr[1] + …. arr[n - 3] - (n - 1)*arr[n-2] + arr[n-1]

Generalising the equation,

sum(k) - sum(k-1) = arr[0] + arr[1] + …. Arr[n - 1] - (n)*arr[n - k]

Using this we can find the value of sum(k) using sum(0),

Now, in the solution we will find the sum of all values of the array, then find the value of sum(0). Using a loop, we will find all values of sum(k) from 1 to n. And return the maximum of them.

Program to illustrate the working of our solution,

Example

 Live Demo

#include <iostream>
using namespace std;
int findMaxSumRotation(int arr[], int n){
   int arrSum = 0;
   int currSum = 0;
   for (int i=0; i<n; i++){
      arrSum = arrSum + arr[i];
      currSum = currSum+(i*arr[i]);
   }
   int maxSum = currSum;
   for (int j=1; j<n; j++){
      currSum = currSum + arrSum-n*arr[n-j];
      if (currSum > maxSum)
         maxSum = currSum;
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 1, 3, 7, 2};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum value of sum(i*arr[i]) using rotations is "<<findMaxSumRotation(arr, n);
   return 0;
}

Output

The maximum value of sum(i*arr[i]) using rotations is 43