New update is available. Click here to update.

Maximum Sum Of (i * ARR[i]) Among All Possible Rotations Of An Array

MEDIUM

15 mins

11 upvotes

Arrays

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Maximum Sum Of (i * ARR[i]) Among All Possible Rotations Of An Array

Contributed by

Ayush Thakur

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 15 mins

Success Rate 85 %

11 upvotes

Problem Statement

You are given an array 'ARR' consisting of 'N' elements, and you need to find the maximum value of sum(i * ARR[i]) among all possible rotations of the given array. The rotations allowed are left rotation, and right rotation, and these rotations can be performed any number of times on the array.

Sum(i * ARR[i]) denotes the summation of all values (i * ARR[i]) for every 'i', where 0 <= 'i' <= 'N' - 1.

Note :

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.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

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.

Output Format :

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

Note :

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

Constraints :

1 <= T <= 10^2
1 <= N <= 10^4
0 <= ARR[i] <= 10^6

Time Limit : 1sec

Sample Input 1 :

1
5
1 5 2 10 0

Sample Output 1 :

Explanation For Sample Input 1 :

Sum of all i*ARR[i] values after 'X' rotations are as follows:
After 0 rotations (original array): 0*1 + 1*5 + 2*2 + 3*10 + 4*0 = 39.
We are choosing to rotate left.
After 1 rotation to the left on the original array: 0*5 + 1*2 + 2*10 + 3*0 + 4*1 = 26.
After 2 rotations to the left on the original array: 0*2 + 1*10 + 2*0 + 3*1 + 4*5 = 33.
After 3 rotations to the left on the original array: 0*10 + 1*0 + 2*1 + 3*5 + 4*2 = 25.  
After 4 rotations to the left on the original array: 0*0 + 1*1 + 2*5 + 3*2 + 4*10 = 57.
57 is the maximum value of sum(i*ARR[i]) among all rotations of the given array.

Sample Input 2 :

1
4
1 2 3 4

Sample Output 2 :

Explanation For Sample Input 2 :

The original array has the maximum sum among all possible rotations of the array. The original array sums to 20, as 1*0 + 2*1 + 3*2 + 4*3 = 20.

Auto

Console