Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed

0 0 9 minutes read

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 = 72

Input: 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 case
arr = [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

Time Complexity: O(N²), 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 R_j 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 R_j from R_j-1.

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?

This can be done in O(1) time. Below are the details.

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 = 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) = 330

Previous 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 R₀ 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 program
int 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) function
if __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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!