# Find the Maximum Sum of i*arr[i] Among all Possible Rotations of an Array

## Introduction

How often do you encounter problems that involve maximizing the value of a given function? It seems complicated to many people, but if one tends to analyze the functions properly, it won’t be too hard to figure out how to maximize it.

Source: __Link__

The problem of finding the maximum sum of **i*arr[i]** among all possible rotations on a given array is a similar maximization problem.

Let’s look at the problem statement once. So we are given an array of integers. We need to find the maximum sum of** i*arr[i],** where i is the index, given that you can rotate the array any number of times.

Let’s look at an example where we will get more clarity of the problem.

Let’s say, we have an array of size N = 4,

Let’s say, we have an array of size N = 4,

and array is

Now let’s see all possible rotations and calculate the sum of **i*arr[i]** in each rotation.

**How many rotations are possible**?

We can make at most **N** rotations including the initial array to get a different array every time in general. Because if more than **N** rotations are considered, then we will be reconsidering already considered rotations.

- Rotating for the first time, the array will become as :

- Rotating for the second time, the array will become as :

- Rotating for the third time, the array will become as :

- Rotating for the fourth time, the array will become as :

From the four rotations, which rotation returns the maximum sum of i*arr[i]?

It is after the first rotation that the value is maximum, which is **71**.

Hence the answer is **71**.

I hope you got the essence of the problem from the above example. If not, then no worries, now we will discuss the approach.

Approach

Let’s look at the most trivial approach that comes to our mind first.

Calculating the sum of i*arr[i] in each rotation and maximize it.

So the approach becomes simple.

- Calculate the value of the sum of
**i*arr[i]**. - Maximize the sum, and rotate the array.
- Repeat the process until the number of rotations is not greater than
**N**.

**NOTE**: if the number of rotations **R** is greater than **N,** then **R** should be taken as** N** only as the array after **R** rotations is the same as after **R%N** rotations.

Don’t worry about the time complexity here; we will have a look at it later on.

## PseudoCode

#Assume there is a function sumOfProducts(arr, n) that computes sum of i*arr[i].

**Algorithm**

___________________________________________________________________

**procedure** maxSumOfProducts(arr, n):

___________________________________________________________________

**1.** maxSum ← -∞** #** **assume answer to be -inf**

**2.** rotations ← 0 **# to keep track of rotations**

**3.** **while** rotations < n **do # run till n rotations**

**4. **rotateArray(arr, n) **#** **rotate the array**

**5.** rotatedArraySum ← sumOfProducts(arr, n) **#compute the sum i*arr[i]**

**6.** **if ** rotatedArraySum > maxSum **do #update the maximum sum**

**7.** ** **maxSum ← rotatedArraySum

**8. end if**

**9. **rotations ← rotations + 1 **# increment the count of rotations **

**10.** **end while**

**11. return **maxSum **#return the maximum sum.**

**12.end procedure**

___________________________________________________________________

## CODE IN C++

//C++ program to find maximum value of sum of i*arr[i] #include <bits/stdc++.h> using namespace std;
// function to rotate the given array by 1 rotation void rotateArray(int arr[], int n) { // temporary array to store the rotated elements int temp[n];
// loop to store the elements in temp array for (int i = 0; i < n; ++i) { temp[(i + 1) % n] = arr[i]; }
// loop to restore the rotated elements in original array for (int i = 0; i < n; ++i) { arr[i] = temp[i]; } }
// function that returns the sum of i*arr[i] of an array int sumOfProducts(int arr[], int n) { int sum = 0; for (int i = 0; i < n; ++i) { sum += i * arr[i]; } return sum; }
//function that computes the maximum value of sum of i*arr[i] int maxSumOfProducts(int arr[], int n) { // initializing answer to be -infinity int maxSum = INT_MIN;
// to keep track of rotations int rotations = 0;
// run till n rotations while (rotations < n) { // rotate the array. rotateArray(arr, n);
// find sumOfProducts int rotatedArraySum = sumOfProducts(arr, n);
// update the maximum sum if (rotatedArraySum > maxSum) maxSum = rotatedArraySum;
// increment the number of rotations. rotations = rotations + 1; }
//return maximum Sum of i*arr[i] return maxSum; }
int main() { int n = 4; int arr[] = {1, 20, 10, 2}; cout << "The maximum value of sum of i*arr[i] = " << maxSumOfProducts(arr, n) << '\n'; return 0; } |

**Output**

The maximum value of sum of i*arr[i] = 71 |

### Time Complexity

O(n^{2}) because we are traversing the array again in each rotation for computing the sum of i*arr[i], which takes O(n) time. For n rotations will take O(n^{2}) time to compute the maximum sum of i*arr[i] using the above algorithm.

### Space complexity

O(n), as we are rotating the array.

Rotating the array repeatedly and computing the sum of products takes a lot of time as it does redundant work. So can we come up with some efficient approach that does the same job in less time?

Source: __link__

So, let's discuss how we can optimize the solution for the problem.

## Approach to a Time-efficient Solution

Now the very first question is, where are we consuming time?

(**Note**: It’s imperative to understand and find the root cause of the problem before directly jumping on to its solution.)

We are taking time to rotate the array repetitively and computing the sum of products again and again.

Now the question arises which repetition should we remove first? Should we remove any repetitive work, i.e., either computing the sum of products or avoiding rotating the array.

We will have to calculate the sum for every rotation, so if we can somehow sum up each rotation of the array efficiently, we can significantly reduce the repetitive work.

To compute the sum efficiently, we need to observe how the sum changes with each rotation.

Let’s say after **r** rotations, we have the array, which looks like:

**A _{r}** = {

**a**}

_{0}, a_{1}….., a_{n-2}, a_{n-1}**S _{r }** =

**0*a**

_{0}+ 1*a_{1}+.. + (n-2)*a_{n-2}+ (n-1)*a_{n-1}

Now, after** r+1** rotations, we have the array which looks like,

**A _{r+1}** = {

**a**}

_{ n-1}, a_{0}….. a_{n-3}, a_{n-2}**S _{r+1 }** =

**0*a**

_{n-1}+ 1*a_{0}+.. + (n-2)*a_{n-3}+ (n-1)*a_{n-2}

Can we observe some relation between the terms **S _{ r+1}** and

**S**?

_{r }

Let’s try to find some relation between the 2 terms. So if we are given a sum of **r ^{th} **rotation and want to compute the

**(r+1)**rotation, we will have to add or subtract some term to it.

_{th}

Let’s say,

S = _{ r+1}C*S_{r }+ X, where C is some constant |

This is because it will not be correct if we simply write C = 1 initially. We can put the value of C later on according to our convenience, which simplifies our computation, and we can get to a good relationship between them.

Note that we also want to compute X, so the logical thing is to subtract

**S _{ r+1}** and

**C*S**

_{r.}

** _{ }S_{ r+1 }**-

**C*S**

_{r }= (0*a_{n-1}+ 1*a_{0}+.. + (n-2)*a_{n-3}+ (n-1)*a_{n-2}) - C*(0*a_{0}+ 1*a_{1}+.. + (n-2)*a_{n-2}+ (n-1)*a_{n-1})

**S _{ r+1 }**-

**C*S**

_{r }= ((1-0*C)*a_{0}+ (2-1*C)a_{1}+.. (n-1 -(n-2)*C)a_{n-2}+ (0 - (n-1)*C)a_{n-1})

Now, we can put C = 1 because X is also dependent on C, so removing the term C from our equation will make it easier to understand.

**S _{ r+1 }**-

**S**

_{r}= (a_{0}+ (2-1)a_{1 }..+.. (n-1 -n+2)a_{n-2}+ (-(n-1))a_{n-1})** = a _{0} + a_{1} + …. + a_{n-2} + (1-n)*a_{n-1}**

_{= }a_{0} + a_{1} + …. + a_{n-2} + a _{n-1} - n*a _{n-1}

**= sumOfArray - n*a _{n-1}**

Another thing to look at is that **a _{n-1}** will keep changing with each rotation, so we must take care of that.

After **r ^{th}** rotation,

**a**as the previous element shifts by one position with each rotation. Hence we derived the value of

_{n-1}= a_{ n-r}**a**

_{n-1}.Therefore, **S _{ r+1 }**-

**S**

_{r}= sumOfArray - n*a_{n-r}Now, this simplifies our result, i.e., we just need to compute the sum of the array once, and the rest is adding the subtraction result to **S _{r}. **

Now for each rotation, we have the sum using the above result.

Source: __link__

### Algorithm(space and time optimized)

- Compute the sum of the array initially.
- For each rotation, compute the sum using the above result
- Maximize the result and repeat the process until all the rotations are covered.

I guess the algorithm says it all. There’s no need for giving another pseudoCode because all the techniques are pretty familiar to us. Hence we can jump onto the coding part now. (Don’t worry, the code part will be self-explanatory).

## CODE IN C++(Space and Time Optimized)

//C++ program to find minimum number of swaps #include <bits/stdc++.h> using namespace std;
// function that computes the maximum value of sum of i*arr[i] int maxSumOfProducts(int arr[], int n) { // to store the sum of given array int sumOfarray = 0;
// to store the sum of i*arr[i] for given array after rotation. int curSumofproducts = 0;
for (int i = 0; i < n; ++i) { // add arr[i] to sumOfarray sumOfarray += arr[i];
// add i*arr[i] to cur rotation sum curSumofproducts += i * arr[i]; }
// to store the maxSum int maxSum = curSumofproducts;
// count of rotation is 1 as we already have products sum of a rotation -> of given array int rotations = 1;
// compute the sum of current rotation while (rotations < n) { curSumofproducts += sumOfarray - n * arr[n - rotations];
// maximise the sum maxSum = max(maxSum, curSumofproducts);
// increment rotations rotations = rotations + 1; } // return the maximum sum. return maxSum; }
int main() { int n = 4; int arr[] = {1, 20, 10, 2}; cout << "The maximum value of sum of i*arr[i] = " << maxSumOfProducts(arr, n) << '\n'; return 0; } |

**Output**

The maximum value of sum of i*arr[i] = 71 |

### Time Complexity

O(n) because we are computing the sum of each rotation in O(1) time, and the only time taken is to calculate the sum of the array once and iterating over all rotations. Hence the time complexity is O(n).

### Space complexity

O(1), as no extra auxiliary space is used.

## Frequently Asked Questions

**How to find the element at a given index after r rotations?**

**Answer) **Let **r** be the number of** **rotations and **n** be the size of the array. Let **i_old** be the index before rotation and **i_after** be the index after rotation. Then we have

i_after = (i_old + r) % n |

**How do you find the maximum sum of an array?**

**Answer) **The maximum sum of an array is a very common problem that is solved using Kadane’s Algorithm. To know more about Kadane’s Algorithm, refer __here__.

**How do you find the minimum sum of an array?**

**Answer) **The minimum sum of an array is a common application of Kadane’s algorithm where we minimize the result at each iteration.

## Key Takeaways

This article taught us how to maximize the sum of i*arr[i] by approaching the problem using a brute force approach to the most optimal approach finally. We discussed their implementation using an iterative method using illustrations, through pseudocode, and then proper code. We hope you were able to take away critical techniques like analyzing problems by writing some mathematical formulations and manipulating them, which simplifies the results to a greater extent.

Now, we recommend you practice problem sets based on maximization problems to master your fundamentals. You can get a wide range of questions similar to the problem __maximum sum of i*arr[i]__ on __CodeStudio__.

Comments

## No comments yet

## Be the first to share what you think