New update is available. Click here to update.

Last Updated: 26 Nov, 2020

Difficulty: Moderate

```
1. The array follows 0-based indexing.
2. In one rotation operation, all elements of the array will shift either towards the left or right by one index.
3. The element at the extreme left index (i.e. 0th index) will shift to the 'N-1'th index after applying one left rotation on the array and the rest all the elements will shift to the 'i-1'th index.
4. The element at the extreme right index (i.e. 'N-1'th index) will shift to the 0th index after applying one right rotation on the array and the rest of the elements will shift to the 'i' + 1'th index.
```

```
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains the integer 'N', denoting the size of the array.
The second line of each test case contains 'N' space-separated integers denoting the array elements.
```

```
The only line of output of each test case should contain an integer, denoting the maximum value of sum(i * ARR[i]).
```

```
You don't need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10^2
1 <= N <= 10^4
0 <= ARR[i] <= 10^6
Time Limit : 1sec
```

It’s important to note that, there are only a finite number of unique arrangments of the array possible after applying rotation operations on the array any number of times. So what we can do is find the sum(i*ARR[i]) for all possible rotations and return the maximum among them.

Here is the algorithm :

- Create a variable (say, ‘maxSum’) and initialise it to 0.
- Run a loop from 0 to 'N - 1' (say, iterator ‘i’), as these are all possible starting indices of the array in some rotation or the other.
- For each starting index, calculate the ending index of the array possible as ‘endIndex’ = (i + N - 1) % N (because the size of the array is ‘N’) and store the current array sum in variable (say, ‘currentSum’)
- Iterate from starting index to next 'N - 1'(valid) indices by calculating the next index as (i + 1) % N till you reach end index and update the ‘currentSum’ by adding 'i * ARR[i]'.
- After reaching the end index update ‘maxSum’ to maximum of 'maxSum' and ‘currentSum’.
- Finally, return the maximum sum after all iterations of i.

It’s important to note that, there are limited arrays possible after applying rotation operations on the array any number of times. Also notice that 1 left rotation = ‘N - 1' right rotations and vice versa, thus we can choose a single type of rotation and fetch all possible arrangments of the given array.

Here is the algorithm :

- Create a variable (say, ‘originalArraySum’) and initialise it to 0.
- In this method, we will try to find a relation between sum(i*ARR[i]) values of two consecutive rotations of an array. These can be either two consecutive left rotations or two consecutive right rotations.
- Let’s assume that, given array ‘ARR’ is {ARR[0], ARR[1], …… ARR[N - 1]}.
- We will denote sum after i rotations on the original array as SR(i).
- Then SR(0) = 0*ARR[0] + 1*ARR[1] + ….. (N - 1)*ARR[N - 1].
- Let’s assume we choose to apply left rotations on array only.
- Then, SR(1) = 0*ARR[1] + 1*ARR[2] + ……. (N - 1)*ARR[0].
- Then the value of SR(1) - SR(0) will be ARR[2] + ARR[3] + … + (N - 1)*ARR[0] - ARR[1] - ARR[2] - …. - (N - 1)*ARR[N - 1].
- Also, note that SR(1) = SR(0) - ‘originalArraySum’ + N * Arr[0].
- Thus, SR(1) - SR(0) can be rewritten as, N*ARR[0] - ‘originalArraySum’.
- So, for any number of rotations j from 1 to 'N - 1' in the given ARR[],
- SR(j) can be calculated as:
- SR(j) = SR(j - 1) - ‘originalArraySum’ + N*ARR[j - 1].
- Thus we can find the sum(i*ARR[i]) for the original array, and can update this sum for all possible arrangments in O(N) time and find the maximum.

SIMILAR PROBLEMS

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Three Sum

Posted: 24 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Sort 0s, 1s, 2s

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: