Method 2: This method discusses the efficient solution which solves the problem in O(n) time. In the naive solution, the values were calculated for every rotation. So if that can be done in constant time then the complexity will decrease.
- Approach: The basic approach is to calculate the sum of new rotation from the previous rotations. This brings up a similarity where only the multipliers of first and last element change drastically and the multiplier of every other element increases or decreases by 1. So in this way, the sum of next rotation can be calculated from the sum of present rotation.
-
Algorithm:
The idea is to compute the value of a rotation using values of previous rotation. When an array is rotated by one, following changes happen in sum of i*arr[i].- Multiplier of arr[i-1] changes from 0 to n-1, i.e., arr[i-1] * (n-1) is added to current value.
- Multipliers of other terms is decremented by 1. i.e., (cum_sum – arr[i-1]) is subtracted from current value where cum_sum is sum of all numbers.
next_val = curr_val - (cum_sum - arr[i-1]) + arr[i-1] * (n-1); next_val = Value of ∑iarr[i] after one rotation. curr_val = Current value of ∑iarr[i] cum_sum = Sum of all array elements, i.e., ∑arr[i]. Lets take example {1, 2, 3}. Current value is 10+21+32 = 8. Shifting it by one will make it {2, 3, 1} and next value will be 8 - (6 - 1) + 12 = 5 which is same as 20 + 31 + 1*2
- Implementation:
- C++
// An efficient C++ program to compute
// maximum sum of i*arr[i]
#include<bits/stdc++.h>
using namespace std;
int maxSum( int arr[], int n)
{
`` // Compute sum of all array elements
`` int cum_sum = 0;
`` for ( int i=0; i<n; i++)
`` cum_sum += arr[i];
`` // Compute sum of i*arr[i] for initial
`` // configuration.
`` int curr_val = 0;
`` for ( int i=0; i<n; i++)
`` curr_val += i*arr[i];
`` // Initialize result
`` int res = curr_val;
`` // Compute values for other iterations
`` for ( int i=1; i<n; i++)
`` {
`` // Compute next value using previous
`` // value in O(1) time
`` int next_val = curr_val - (cum_sum - arr[i-1])
`` + arr[i-1] * (n-1);
`` // Update current value
`` curr_val = next_val;
`` // Update result if required
`` res = max(res, next_val);
`` }
`` return res;
}
// Driver code
int main()
{
`` int arr[] = {8, 3, 1, 2};
`` int n = sizeof (arr)/ sizeof (arr[0]);
`` cout << maxSum(arr, n) << endl;
`` return 0;
}
Output:
29
-
Complexity analysis:
-
Time Complexity: O(n).
Since one loop is needed from 0 to n to check all rotations and the sum of the present rotation is calculated from the previous rotations in O(1) time). -
Auxiliary Space: O(1).
As no extra space is required to so the space complexity will be O(1)
-
Time Complexity: O(n).