Given an array arr[] of n integers, find the maximum that maximizes the sum of the value of i*arr[i] where i varies from 0 to n-1.
Examples:
Input: arr[] = {8, 3, 1, 2} Output: 29 Explanation: Lets look at all the rotations, {8, 3, 1, 2} = 80 + 31 + 12 + 23 = 11 {3, 1, 2, 8} = 30 + 11 + 22 + 83 = 29 {1, 2, 8, 3} = 10 + 21 + 82 + 33 = 27 {2, 8, 3, 1} = 20 + 81 + 32 + 13 = 17 Input: arr[] = {3, 2, 1} Output: 7 Explanation: Lets look at all the rotations, {3, 2, 1} = 30 + 21 + 12 = 4 {2, 1, 3} = 20 + 11 + 32 = 7 {1, 3, 2} = 10 + 31 + 2*2 = 7
Method 1:
This method discusses the Naive Solution which takes O(n2) amount of time.
The solution involves finding the sum of all the elements of the array in each rotation and then deciding the maximum summation value.
-
Approach:
A simple solution is to try all possible rotations. Compute sum of i*arr[i] for every rotation and return maximum sum. -
Algorithm:
- Rotate the array for all values from 0 to n.
- Calculate the sum for each rotations.
- Check if the maximum sum is greater than the current sum then update the maximum sum.
- Implementation:
- C++
// A Naive C++ program to find maximum sum rotation
#include<bits/stdc++.h>
using namespace std;
// Returns maximum value of i*arr[i]
int maxSum( int arr[], int n)
{
`` // Initialize result
`` int res = INT_MIN;
`` // Consider rotation beginning with i
`` // for all possible values of i.
`` for ( int i=0; i<n; i++)
`` {
`` // Initialize sum of current rotation
`` int curr_sum = 0;
`` // Compute sum of all values. We don't
`` // acutally rotation the array, but compute
`` // sum by finding ndexes when arr[i] is
`` // first element
`` for ( int j=0; j<n; j++)
`` {
`` int index = (i+j)%n;
`` curr_sum += j*arr[index];
`` }
`` // Update result if required
`` res = max(res, curr_sum);
`` }
`` 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(n2)
- Auxiliary Space : O(1)