Given an array arr[] of size N, the task is to find the maximum possible sum of i*arr[i] when the array can be rotated any number of times.
Examples :
Input: arr[] = {1, 20, 2, 10}
Output: 72.We can get 72 by rotating array twice.
{2, 10, 1, 20}
20*3 + 1*2 + 10*1 + 2*0 = 72Input: arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Output: 330
We can get 330 by rotating array 9 times.
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
0*1 + 1*2 + 2*3 … 9*10 = 330
Naive Approach: The basic idea of this approach is
Find all rotations one by one, check the sum of every rotation and return the maximum sum.
Algorithm
- Start by initializing max_sum to INT_MIN
- Loop say i,from 0 to n-1:
- a. Initialize sum to 0
- b. Loop j from 0 to n-1:
- i. Calculate the index of the j-th element after rotation: (i+j) % n
- ii. Add the product of the element and its index to sum: j * arr[(i+j) % n]
- c. If sum is greater than max_sum, update max_sum to sum
- Return max_sum
C++
#include <climits>#include <iostream>using namespace std;int max_sum_rotation(int arr[], int n){ int max_sum = INT_MIN; // set the maximum sum to the // minimum possible value for (int i = 0; i < n; i++) { // loop through all possible rotations int sum = 0; // set the current sum to zero for (int j = 0; j < n; j++) { // loop through all elements in the // array int index = (i + j) % n; // calculate the index of the current // element after rotation sum += j * arr[index]; // add the product of the // element with its index // to the sum } max_sum = max( max_sum, sum); // update the maximum sum if necessary } return max_sum; // return the maximum sum obtained over // all rotations}int main(){ int arr[] = { 10, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // define an array int n = sizeof(arr) / sizeof( arr[0]); // calculate the size of the array cout << max_sum_rotation(arr, n) << endl; // call the function and print the result return 0; // indicate successful program completion} |
Java
/*package whatever //do not write package name here */import java.io.*;public class MaxSumRotation { public static int maxSumRotation(int[] arr, int n) { // Set the maximum sum to the minimum possible value int maxSum = Integer.MIN_VALUE; // Loop through all possible rotations for (int i = 0; i < n; i++) { // Set the current sum to zero int sum = 0; // Loop through all elements in the array for (int j = 0; j < n; j++) { // Calculate the index of the current element after rotation int index = (i + j) % n; // Add the product of the element with its index to the sum sum += j * arr[index]; } // Update the maximum sum if necessary maxSum = Math.max(maxSum, sum); } // Return the maximum sum obtained over all rotations return maxSum; } public static void main(String[] args) { int[] arr = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}; int n = arr.length; System.out.println(maxSumRotation(arr, n)); }} |
Python3
def max_sum_rotation(arr, n): # set the maximum sum to the # minimum possible value max_sum = float('-inf') # loop through all possible rotations for i in range(n): # set the current sum to zero sum = 0 # loop through all elements in the array for j in range(n): # calculate the index of the current element after rotation index = (i + j) % n # add the product of the element with its index to the sum sum += j * arr[index] # update the maximum sum if necessary max_sum = max(max_sum, sum) # return the maximum sum obtained over all rotations return max_sum# Test casearr = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]n = len(arr)print(max_sum_rotation(arr, n)) |
Javascript
function maxSumRotation(arr) { const n = arr.length; let maxSum = Number.MIN_SAFE_INTEGER; for (let i = 0; i < n; i++) { let sum = 0; for (let j = 0; j < n; j++) { const index = (i + j) % n; sum += j * arr[index]; } maxSum = Math.max(maxSum, sum); } return maxSum;}const arr = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9];console.log(maxSumRotation(arr)); |
Output
330
Time Complexity: O(N2), where n is the size of the input array.
Auxiliary Space: O(1), because it uses a constant amount of extra space to store the variables max_sum, sum, i, and j.
Efficient Approach: The idea is as follows:
Let Rj be value of i*arr[i] with j rotations.
- The idea is to calculate the next rotation value from the previous rotation, i.e., calculate Rj from Rj-1.
- We can calculate the initial value of the result as R0, then keep calculating the next rotation values.
How to efficiently calculate Rj from Rj-1?
This can be done in O(1) time. Below are the details.
Let us calculate initial value of i*arr[i] with no rotation
R0 = 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.
- R1 = 0*arr[n-1] + 1*arr[0] +…+ (n-1)*arr[n-2]
- R1 – R0 = 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.
- R2 = 0*arr[n-2] + 1*arr[n-1] +…+ (n-1)*arr[n-3]
- R2 – R1 = 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
Rj – Rj-1 = arrSum – n * arr[n-j],
Where arrSum is sum of all array elements, i.e., arrSum = ∑ arr[i] , 0 ≤ i ≤ N-1
Follow the below illustration for a better understanding.
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 = 285 + 55 – (10 * 8) = 260
3rd rotation: currVal = 285 + 55 – (10 * 7) = 270
.
.
.
Last rotation: currVal = 285 + 55 – (10 * 1) = 330Previous currVal was 285, now it becomes 330.
It’s the maximum value we can find hence return 330.
Follow the steps mentioned below to implement the above approach:
- Compute the sum of all array elements. Let this sum be ‘arrSum‘.
- Compute R0 for the given array. Let this value be currVal.
- Loop from j = 1 to N-1 to calculate the value for each rotation:
- Update the currVal using the formula mentioned above.
- Update the maximum sum accordingly in each step.
- Return the maximum value as the required answer.
Below is the implementation of the above idea.
C++
// C++ program to find max value of i*arr[i]#include <iostream>using namespace std;// Returns max possible value of i*arr[i]int maxSum(int arr[], int n){ // Find array sum and i*arr[i] with no rotation int arrSum = 0; // Stores sum of arr[i] int currVal = 0; // Stores sum of i*arr[i] for (int i = 0; i < n; i++) { arrSum = arrSum + arr[i]; currVal = currVal + (i * arr[i]); } // Initialize result as 0 rotation sum int maxVal = currVal; // Try all rotations one by one and find // the maximum rotation sum. for (int j = 1; j < n; j++) { currVal = currVal + arrSum - n * arr[n - j]; if (currVal > maxVal) maxVal = currVal; } // Return result return maxVal;}// Driver programint main(void){ int arr[] = { 10, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "\nMax sum is " << maxSum(arr, n); return 0;} |
Java
// Java program to find max value of i*arr[i]import java.util.Arrays;class Test { static int arr[] = new int[] { 10, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // Returns max possible value of i*arr[i] static int maxSum() { // Find array sum and i*arr[i] with no rotation int arrSum = 0; // Stores sum of arr[i] int currVal = 0; // Stores sum of i*arr[i] for (int i = 0; i < arr.length; i++) { arrSum = arrSum + arr[i]; currVal = currVal + (i * arr[i]); } // Initialize result as 0 rotation sum int maxVal = currVal; // Try all rotations one by one and find // the maximum rotation sum. for (int j = 1; j < arr.length; j++) { currVal = currVal + arrSum - arr.length * arr[arr.length - j]; if (currVal > maxVal) maxVal = currVal; } // Return result return maxVal; } // Driver method to test the above function public static void main(String[] args) { System.out.println("Max sum is " + maxSum()); }} |
Python
'''Python program to find maximum value of Sum(i*arr[i])'''# returns max possible value of Sum(i*arr[i])def maxSum(arr): # stores sum of arr[i] arrSum = 0 # stores sum of i*arr[i] currVal = 0 n = len(arr) for i in range(0, n): arrSum = arrSum + arr[i] currVal = currVal + (i*arr[i]) # initialize result maxVal = currVal # try all rotations one by one and find the maximum # rotation sum for j in range(1, n): currVal = currVal + arrSum-n*arr[n-j] if currVal > maxVal: maxVal = currVal # return result return maxVal# test maxsum(arr) functionif __name__ == '__main__': arr = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] print "Max sum is: ", maxSum(arr) |
C#
// C# program to find max value of i*arr[i]using System;class Test { static int[] arr = new int[] { 10, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // Returns max possible value of i*arr[i] static int maxSum() { // Find array sum and i*arr[i] // with no rotation int arrSum = 0; // Stores sum of arr[i] int currVal = 0; // Stores sum of i*arr[i] for (int i = 0; i < arr.Length; i++) { arrSum = arrSum + arr[i]; currVal = currVal + (i * arr[i]); } // Initialize result as 0 rotation sum int maxVal = currVal; // Try all rotations one by one and find // the maximum rotation sum. for (int j = 1; j < arr.Length; j++) { currVal = currVal + arrSum - arr.Length * arr[arr.Length - j]; if (currVal > maxVal) maxVal = currVal; } // Return result return maxVal; } // Driver Code public static void Main() { Console.WriteLine("Max sum is " + maxSum()); }}// This article is contributed by vt_m. |
Javascript
<script>// JavaScript program to find max value of i*arr[i]// Returns max possible value of i*arr[i]function maxSum(arr, n){ // Find array sum and i*arr[i] with no rotation let arrSum = 0; // Stores sum of arr[i] let currVal = 0; // Stores sum of i*arr[i] for (let i=0; i<n; i++) { arrSum = arrSum + arr[i]; currVal = currVal+(i*arr[i]); } // Initialize result as 0 rotation sum let maxVal = currVal; // Try all rotations one by one and find // the maximum rotation sum. for (let j=1; j<n; j++) { currVal = currVal + arrSum-n*arr[n-j]; if (currVal > maxVal) maxVal = currVal; } // Return result return maxVal;}// Driver program let arr = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]; let n = arr.length; document.write("Max sum is " + maxSum(arr, n));// This code is contributed by Surbhi Tyagi.</script> |
PHP
<?php// PHP program to find max // value of i*arr[i] // Returns max possible // value of i*arr[i]function maxSum($arr, $n){ // Find array sum and // i*arr[i] with no rotation // Stores sum of arr[i] $arrSum = 0; // Stores sum of i*arr[i] $currVal = 0; for ($i = 0; $i < $n; $i++) { $arrSum = $arrSum + $arr[$i]; $currVal = $currVal + ($i * $arr[$i]); } // Initialize result as // 0 rotation sum $maxVal = $currVal; // Try all rotations one // by one and find the // maximum rotation sum. for ($j = 1; $j < $n; $j++) { $currVal = $currVal + $arrSum - $n * $arr[$n - $j]; if ($currVal > $maxVal) $maxVal = $currVal; } // Return result return $maxVal;}// Driver Code$arr = array (10, 1, 2, 3, 4, 5, 6, 7, 8, 9);$n = sizeof($arr);echo "Max sum is " , maxSum($arr, $n);// This code is contributed by m_kit?> |
Output
Max sum is 330
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
