Last Updated: 23 Aug, 2021
Maximum Sum
Moderate
Asked in companies
You are given an array ‘arr’ consisting of ‘N’ integers. Your task is to maximize the value of 0 * arr[0] + 1 * arr[1] + 2 * arr[2] … (N - 1) * arr[N - 1] . You can rotate the array as many times as you wish.
For Example:
For the given arr[ ] = { 1, 2, 3, 1}
After 0 rotation arr[ ] = { 1, 2, 3, 1} the sum is = (0 *1 + 1 * 2 + 2 * 3 + 3 * 1) = 11.
After 1 rotation arr[ ] = { 1, 1, 2, 3} the sum is = (0 *1 + 1 * 1 + 2 * 2 + 3 * 3) = 14.
After 2 rotation arr[ ] = { 3, 1, 1, 2} the sum is = (0 *3 + 1 * 1 + 2 * 1 + 3 * 2) = 9.
After 3 rotation arr[ ] = { 2, 3, 1, 1} the sum is = (0 *2 + 1 * 3 + 2 * 1 + 3 * 1) = 8.
So the maximum sum is 14 when arr[ ] = { 1, 1, 2, 3}.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.
The first line of each test case contains the Integer ‘N’ denoting the number of elements in the array.
The second and the last line of each test case contains ‘N’ single space-separated integers representing the elements of the array.
Output Format:
For each test case, print an integer representing the maximum value of 0 * arr[0] + 1 * arr[1] + 2 * arr[2] … (N - 1) * arr[N - 1].
The output of each test case will be printed on a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 5 * 10 ^ 6
-10 ^ 5 <= arr[i] <= 10 ^ 5
Time Limit: 1 sec.
Approaches
The idea is to try out all possible rotations and find the value 0 * arr[0] + 1 * arr[1] + 2 * arr[2] … (N - 1) * arr[N - 1]. We will iterate ‘i’ from 0 to N.
- The position of the element at index ‘j’ would become (i + j) % N.
- We will compute the sum, and the maximum value of all possible rotations would be our required answer.
Algorithm :
The steps are as follows:
- Take a variable ‘res’ and initialize it to a minimum integer value.
- Iterate ‘i’ from 0 to ‘N’, to consider all possible rotation
- Take a variable ‘currSum’ and initialize it to 0.
- Iterate ‘j’ from 0 to ‘N’ to compute the sum of all values as given in the question:
- Take a variable ‘index’ and initialize it to (i + j) % N.
- Increment ‘currSum’ by j * arr[index].
- Assign ‘res’ as the max of ‘res’ and ‘currSum’.
- Return ‘res’.
The idea is to compute the value of a current rotation using the value of the previous rotation.When an array is rotated by one, the following changes will happen in the previous sum :
- Multiplier of arr[i -1] changes from 0 to N -1, i.e., arr[i -1] * (N -1) is added to the current value.
- Multipliers of other terms are decremented by 1. i.e., (cumSum – arr[i -1]) is subtracted from the current value where ‘cumSum’ is the sum of all numbers.
Algorithm :
- Take a variable 'cumSum', it Stores the sum of all array elements.
- Iterate ‘i’ from 0 to ‘N’:
- Increment ‘cumSum’ by arr[i].
- Take a variable 'currVal', it Stores the initial configuration, initializes it to 0.
- Iterate ‘i’ from 0 to ‘N’:
- Increment ‘cumVal’ by i * arr[i]’.
- Take a variable 'res', initialize it with 'currVal'.
- Iterate ‘i’ from 1 to N and compute values for other rotation:
- Compute next value using previous value as nextVal = currVal - (cumSum - arr[i - 1]) + arr[i - 1] * (N - 1).
- Update current value as currVal = nextVal.
- Update the variable res as the maximum value of res and nextVal.
- Return ‘res’.
Similar problems