Maximum value of Sum(i*arr[i]) with array rotations allowed

Given an array arr[], the task is to determine the maximum possible value of the expression i*arr[i] after rotating the array any number of times (including zero).
Note: In each rotation, every element of the array shifts one position to the right, and the last element moves to the front.

Examples :  

Input: arr[] = [4, 3, 2, 6, 1, 5]
Output: 60
Explanation: After rotating the array 3 times, we get [1, 5, 4, 3, 2, 6]. Now, the sum of i*arr[i] = 0*1 + 1*5 + 2*4 + 3*3 + 4*2 + 5*6 = 0 + 5 + 8 + 9 + 8 + 30 = 60

Input: arr[] = [8, 3, 1, 2]
Output: 29
Explanation: After rotating the array 3 times, we get [3, 1, 2, 8]. Now, the sum of i*arr[i] = 0*3 + 1*1 + 2*2 + 3*8 = 0 + 1 + 4 + 24 = 29.

Input: arr[] = [10, 1, 2, 7, 9, 3]
Output: 105

[Naive Approach] Take Maximum of All Rotations - O(n^2) Time and O(1) Space 

The idea is to check all possible rotations of the array. As on each rotation, the value of the expression changes as the index positions shift. We rotate the array one step at a time and compute the new sum. By tracking the maximum of these sum values, we ensure we capture the best possible configuration.

// C++ Code to find maximum value of Sum of  // i*arr[i] with rotations using Naive Approach #include <iostream> #include <vector> #include <climits> using namespace std; // Function to calculate i*arr[i] // for given array int computeSum(vector<int> &arr) {    int n = arr.size();  int total = 0;  // Calculate the sum of i*arr[i]  for (int i = 0; i < n; i++) {  total += i * arr[i];  }  return total; } // Function to find maximum value of i*arr[i] // after any number of rotations int maxRotateSum(vector<int> &arr) {    int n = arr.size();    int maxVal = INT_MIN;  // Try all rotations  for (int r = 0; r < n; r++) {  // Calculate i*arr[i] for   // current rotation  int currVal = computeSum(arr);  // Update max value  maxVal = max(maxVal, currVal);  // Rotate array by 1 to right  int last = arr[n - 1];  for (int i = n - 1; i > 0; i--) {  arr[i] = arr[i - 1];  }  arr[0] = last;  }  return maxVal; } // Driver code int main() {    vector<int> arr = {4, 3, 2, 6, 1, 5};  cout << maxRotateSum(arr);  return 0; } 

// Java Code to find maximum value of Sum of  // i*arr[i] with rotations using Naive Approach import java.util.*; class GfG {  // Function to calculate i*arr[i]  // for given array  static int computeSum(int[] arr) {  int n = arr.length;  int total = 0;  // Calculate the sum of i*arr[i]  for (int i = 0; i < n; i++) {  total += i * arr[i];  }  return total;  }  // Function to find maximum value of i*arr[i]  // after any number of rotations  static int maxRotateSum(int[] arr) {  int n = arr.length;  int maxVal = Integer.MIN_VALUE;  // Try all rotations  for (int r = 0; r < n; r++) {  // Calculate i*arr[i] for   // current rotation  int currVal = computeSum(arr);  // Update max value  maxVal = Math.max(maxVal, currVal);  // Rotate array by 1 to right  int last = arr[n - 1];  for (int i = n - 1; i > 0; i--) {  arr[i] = arr[i - 1];  }  arr[0] = last;  }  return maxVal;  }  public static void main(String[] args) {  int[] arr = {4, 3, 2, 6, 1, 5};  System.out.println(maxRotateSum(arr));  } } 

# Python Code to find maximum value of Sum of  # i*arr[i] with rotations using Naive Approach # Function to calculate i*arr[i] # for given array def computeSum(arr): n = len(arr) total = 0 # Calculate the sum of i*arr[i] for i in range(n): total += i * arr[i] return total # Function to find maximum value of i*arr[i] # after any number of rotations def maxRotateSum(arr): n = len(arr) maxVal = float('-inf') # Try all rotations for r in range(n): # Calculate i*arr[i] for  # current rotation currVal = computeSum(arr) # Update max value maxVal = max(maxVal, currVal) # Rotate array by 1 to right last = arr[n - 1] for i in range(n - 1, 0, -1): arr[i] = arr[i - 1] arr[0] = last return maxVal if __name__ == "__main__": arr = [4, 3, 2, 6, 1, 5] print(maxRotateSum(arr)) 

// C# Code to find maximum value of Sum of  // i*arr[i] with rotations using Naive Approach using System; class GfG {  // Function to calculate i*arr[i]  // for given array  static int computeSum(int[] arr) {  int n = arr.Length;  int total = 0;  // Calculate the sum of i*arr[i]  for (int i = 0; i < n; i++) {  total += i * arr[i];  }  return total;  }  // Function to find maximum value of i*arr[i]  // after any number of rotations  static int maxRotateSum(int[] arr) {  int n = arr.Length;  int maxVal = int.MinValue;  // Try all rotations  for (int r = 0; r < n; r++) {  // Calculate i*arr[i] for   // current rotation  int currVal = computeSum(arr);  // Update max value  maxVal = Math.Max(maxVal, currVal);  // Rotate array by 1 to right  int last = arr[n - 1];  for (int i = n - 1; i > 0; i--) {  arr[i] = arr[i - 1];  }  arr[0] = last;  }  return maxVal;  }  static void Main(string[] args) {  int[] arr = {4, 3, 2, 6, 1, 5};  Console.WriteLine(maxRotateSum(arr));  } } 

// JavaScript Code to find maximum value of Sum of  // i*arr[i] with rotations using Naive Approach // Function to calculate i*arr[i] // for given array function computeSum(arr) {  let n = arr.length;  let total = 0;  // Calculate the sum of i*arr[i]  for (let i = 0; i < n; i++) {  total += i * arr[i];  }  return total; } // Function to find maximum value of i*arr[i] // after any number of rotations function maxRotateSum(arr) {  let n = arr.length;  let maxVal = -Infinity;  // Try all rotations  for (let r = 0; r < n; r++) {  // Calculate i*arr[i] for   // current rotation  let currVal = computeSum(arr);  // Update max value  maxVal = Math.max(maxVal, currVal);  // Rotate array by 1 to right  let last = arr[n - 1];  for (let i = n - 1; i > 0; i--) {  arr[i] = arr[i - 1];  }  arr[0] = last;  }  return maxVal; } // Driver Code let arr = [4, 3, 2, 6, 1, 5]; console.log(maxRotateSum(arr)); 

60

[Expected Approach] Using Mathematical Formula - O(n) Time and O(1) Space

The idea is to compute the sum of i*arr[i] for each possible rotation without recalculating it from scratch each time. Instead, we calculate the next rotation value from the previous rotation, i.e., calculate R_j from R_j-1. So, we can calculate the initial value of the result as R₀, then keep calculating the next rotation values.

How to Efficiently Calculate R_j from R_j-1? 

Let us calculate initial value of i*arr[i] with no rotation

R₀ = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1]

After 1 rotation arr[n-1], becomes first element of array, 

• arr[0] becomes second element, arr[1] becomes third element and so on.
• R₁ = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2]
• R₁ - R₀ = arr[0] + arr[1] + ... + arr[n-2] - (n-1)*arr[n-1]

After 2 rotations arr[n-2], becomes first element of array, 

• arr[n-1] becomes second element, arr[0] becomes third element and so on.
• R₂ = 0*arr[n-2] + 1*arr[n-1] +...+ (n-1)*arr[n-3]
• R₂ - R₁ = arr[0] + arr[1] + ... + arr[n-3] - (n-1)*arr[n-2] + arr[n-1]

If we take a closer look at above values, we can observe below pattern:

R_j - R_j-1 = totalSum - n * arr[n-j]

Where totalSum is sum of all array elements

Illustration

Given arr[]={10, 1, 2, 3, 4, 5, 6, 7, 8, 9}, |
arrSum = 55, currVal = summation of (i*arr[i]) = 285
In each iteration the currVal is currVal = currVal + arrSum-n*arr[n-j] ,

1st rotation: currVal = 285 + 55 - (10 * 9) = 250

2nd rotation: currVal = 250 + 55 - (10 * 8) = 225

3rd rotation: currVal = 225 + 55 - (10 * 7) = 210
.......

Last rotation: currVal = 285 + 55 - (10 * 1) = 330

Previous currVal was 285, now it becomes 330.

It's the maximum value we can find hence return 330.

Steps to implement the above idea:

• Start by computing the total sum of all elements and the initial value of i * arr[i] as currVal i.e. R₀.
• Initialize maxVal with currVal to track the maximum.
• Loop from j = 1 to n-1 to simulate all possible rotations using a formula.
• In each iteration, update currVal using the formula: currVal = currVal + totalSum - n * arr[n - j].
• After each update, compare and store the maximum value in maxVal.
• Finally, return maxVal which holds the result for the best rotation.

// C++ Code to find maximum value of Sum of  // i*arr[i] with rotations using Optimized Approach #include <iostream> #include <vector> #include <climits> using namespace std; // Function to find maximum value of i*arr[i] // after any number of rotations int maxRotateSum(vector<int> &arr) {  int n = arr.size();  int totalSum = 0;  int currVal = 0;    // Compute initial value of i*arr[i]  // and total sum  for (int i = 0; i < n; i++) {  totalSum += arr[i];  currVal += i * arr[i];  }  // Initialize result with intial sum value  int maxVal = currVal;  // Compute sum values for each configuration   // and update max  for (int j = 1; j < n; j++) {    // Current sum value for current configuration  currVal = currVal + totalSum - n * arr[n - j];  maxVal = max(maxVal, currVal);  }  return maxVal; } // Driver code int main() {    vector<int> arr = {4, 3, 2, 6, 1, 5};  cout << maxRotateSum(arr);  return 0; } 

// Java Code to find maximum value of Sum of  // i*arr[i] with rotations using Optimized Approach class GfG {  // Function to find maximum value of i*arr[i]  // after any number of rotations  static int maxRotateSum(int[] arr) {  int n = arr.length;  int totalSum = 0;  int currVal = 0;    // Compute initial value of i*arr[i]  // and total sum  for (int i = 0; i < n; i++) {  totalSum += arr[i];  currVal += i * arr[i];  }  // Initialize result with intial sum value  int maxVal = currVal;  // Compute sum values for each configuration   // and update max  for (int j = 1; j < n; j++) {    // Current sum value for current configuration  currVal = currVal + totalSum - n * arr[n - j];  maxVal = Math.max(maxVal, currVal);  }  return maxVal;  }  public static void main(String[] args) {  int[] arr = {4, 3, 2, 6, 1, 5};  System.out.println(maxRotateSum(arr));  } } 

# Python Code to find maximum value of Sum of  # i*arr[i] with rotations using Optimized Approach def maxRotateSum(arr): n = len(arr) totalSum = 0 currVal = 0 # Compute initial value of i*arr[i] # and total sum for i in range(n): totalSum += arr[i] currVal += i * arr[i] # Initialize result with intial sum value maxVal = currVal # Compute sum values for each configuration  # and update max for j in range(1, n): # Current sum value for current configuration currVal = currVal + totalSum - n * arr[n - j] maxVal = max(maxVal, currVal) return maxVal if __name__ == "__main__": arr = [4, 3, 2, 6, 1, 5] print(maxRotateSum(arr)) 

// C# Code to find maximum value of Sum of  // i*arr[i] with rotations using Optimized Approach using System; class GfG {  // Function to find maximum value of i*arr[i]  // after any number of rotations  public static int maxRotateSum(int[] arr) {  int n = arr.Length;  int totalSum = 0;  int currVal = 0;    // Compute initial value of i*arr[i]  // and total sum  for (int i = 0; i < n; i++) {  totalSum += arr[i];  currVal += i * arr[i];  }  // Initialize result with intial sum value  int maxVal = currVal;  // Compute sum values for each configuration   // and update max  for (int j = 1; j < n; j++) {    // Current sum value for current configuration  currVal = currVal + totalSum - n * arr[n - j];  maxVal = Math.Max(maxVal, currVal);  }  return maxVal;  }  public static void Main(string[] args) {  int[] arr = {4, 3, 2, 6, 1, 5};  Console.WriteLine(maxRotateSum(arr));  } } 

// JavaScript Code to find maximum value of Sum of  // i*arr[i] with rotations using Optimized Approach function maxRotateSum(arr) {  let n = arr.length;  let totalSum = 0;  let currVal = 0;    // Compute initial value of i*arr[i]  // and total sum  for (let i = 0; i < n; i++) {  totalSum += arr[i];  currVal += i * arr[i];  }  // Initialize result with intial sum value  let maxVal = currVal;  // Compute sum values for each configuration   // and update max  for (let j = 1; j < n; j++) {    // Current sum value for current configuration  currVal = currVal + totalSum - n * arr[n - j];  maxVal = Math.max(maxVal, currVal);  }  return maxVal; } // Driver Code let arr = [4, 3, 2, 6, 1, 5]; console.log(maxRotateSum(arr)); 

60