Tutorialspoint.dev

Maximum sum of i*arr[i] among all rotations of a given array

Given an array arr[] of n integers, find the maximum that maximizes sum of value of i*arr[i] where i varies from 0 to n-1.

Examples :

Input : arr[] = {8, 3, 1, 2}
Output : 29
Explanation : Let us see all rotations
{8, 3, 1, 2} = 8*0 + 3*1 + 1*2 + 2*3 = 11
{3, 1, 2, 8} = 3*0 + 1*1 + 2*2 + 8*3 = 29
{1, 2, 8, 3} = 1*0 + 2*1 + 8*2 + 3*3 = 27
{2, 8, 3, 1} = 2*0 + 8*1 + 3*2 + 1*1 = 17

Input : arr[] = {3, 2, 1}
Output : 7



Method 1 (Naive Solution : O(n2) )
A simple solution is to try all possible rotations. Compute sum of i*arr[i] for every rotation and return maximum sum. Below is the implementation of this idea.

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;
}

Java

// A Naive Java program to find
// maximum sum rotation
import java.util.*;
import java.io.*;
  
class GFG {
  
// Returns maximum value of i*arr[i]
static int maxSum(int arr[], int n)
{
// Initialize result
int res = Integer.MIN_VALUE;
  
// 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 = Math.max(res, curr_sum);
}
  
return res;
}
  
// Driver code
public static void main(String args[])
{
        int arr[] = {8, 3, 1, 2};
        int n = arr.length;
        System.out.println(maxSum(arr, n));
}
  
      
}
  
// This code is contributed by Sahil_Bansall

Python3

# A Naive Python 3 program to find
# maximum sum rotation
import sys
  
# Returns maximum value of i * arr[i]
def maxSum(arr, n):
  
    # Initialize result
    res = -sys.maxsize
  
    # Consider rotation beginning with i
    # for all possible values of i.
    for i in range(0, n):
  
  
        # Initialize sum of current rotation
        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 j in range(0, n):
          
            index = int((i + j)% n) 
            curr_sum += j * arr[index] 
      
  
        # Update result if required
        res = max(res, curr_sum)
    return res 
  
# Driver code
arr = [8, 3, 1, 2
n = len(arr)
  
print(maxSum(arr, n))
  
# This code is contributed by
# Smitha Dinesh Semwal

C#

// A Naive C# program to find
// maximum sum rotation
using System;
  
class GFG {
  
    // Returns maximum value of i*arr[i]
    static int maxSum(int[] arr, int n)
    {
        // Initialize result
        int res = int.MinValue;
  
  
        // 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 = Math.Max(res, curr_sum);
        }
  
        return res;
    }
  
    // Driver code
    public static void Main()
    {
        int[] arr = { 8, 3, 1, 2 };
        int n = arr.Length;
        Console.WriteLine(maxSum(arr, n));
    }
}
  
// This code is contributed by vt_m.

PHP

<?php
// A Naive PHP program to 
// find maximum sum rotation
  
// Returns maximum value
// of i*arr[i]
function maxSum($arr, $n)
{
// Initialize result
$res = PHP_INT_MIN;
  
// Consider rotation beginning 
// with i for all possible 
// values of i.
for ($i = 0; $i < $n; $i++)
{
  
    // Initialize sum of
    // current rotation
    $curr_sum = 0;
  
    // Compute sum of all values.
    // We don't actually rotate 
    // the array, but compute sum
    // by finding indexes when 
    // arr[i] is first element
    for ($j = 0; $j < $n; $j++)
    {
        $index = ($i + $j) % $n;
        $curr_sum += $j * $arr[$index];
    }
  
    // Update result if required
    $res = max($res, $curr_sum);
}
return $res;
}
  
// Driver code
$arr = array(8, 3, 1, 2);
$n = sizeof($arr);
echo maxSum($arr, $n), " ";
  
// This code is contributed by ajit
?>


Output :

29

Time Complexity : O(n2)
Auxiliary Space : O(1)

Method 2 (Efficient Solution : O(n) )
The idea is to compute value of a rotation using value of previous rotation. When we rotate an array by one, following changes happen in sum of i*arr[i].
1) Multiplier of arr[i-1] changes from 0 to n-1, i.e., arr[i-1] * (n-1) is added to current value.
2) 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 &Sum;i*arr[i] after one rotation.
curr_val = Current value of &Sum;i*arr[i] 
cum_sum = Sum of all array elements, i.e., &Sum;arr[i].

Lets take example {1, 2, 3}. Current value is 1*0+2*1+3*2
= 8. Shifting it by one will make it {2, 3, 1} and next value
will be 8 - (6 - 1) + 1*2 = 5 which is same as 2*0 + 3*1 + 1*2

Below is the implementation of this idea.

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;
}

Java

// An efficient Java program to compute
// maximum sum of i*arr[i]
import java.io.*;
  
class GFG {
      
    static 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 = Math.max(res, next_val);
        }
  
        return res;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = {8, 3, 1, 2};
        int n = arr.length;
        System.out.println(maxSum(arr, n));
    }
}
// This code is contributed by Prerna Saini

Python3

# An efficient Python 3 program to
# compute maximum sum of i * arr[i]
  
def maxSum(arr, n):
  
    # Compute sum of all array elements
    cum_sum = 0
      
    for i in range(0, n):
        cum_sum += arr[i] 
  
    # Compute sum of i * arr[i] for 
    # initial configuration.
    curr_val = 0
      
    for i in range(0, n):
        curr_val += i * arr[i] 
  
    # Initialize result
    res = curr_val 
  
    # Compute values for other iterations
    for i in range(1, n):
      
        # Compute next value using previous
        # value in O(1) time
        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
arr = [8, 3, 1, 2
n = len(arr)
  
print(maxSum(arr, n))
  
# This code is contributed by
# Smitha Dinesh Semwal

C#

// An efficient C# program to compute
// maximum sum of i*arr[i]
using System;
  
class GFG {
      
    static 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 = Math.Max(res, next_val);
        }
  
        return res;
    }
  
    // Driver code
    public static void Main()
    {
        int []arr = {8, 3, 1, 2};
        int n = arr.Length;
        Console.Write(maxSum(arr, n));
    }
}
  
// This code is contributed by nitin mittal

PHP

<?php
// An efficient PHP program to 
// compute maximum sum of i*arr[i]
  
function maxSum($arr, $n)
{
    // Compute sum of all
    // array elements
    $cum_sum = 0;
    for ($i = 0; $i < $n; $i++)
        $cum_sum += $arr[$i];
  
    // Compute sum of i*arr[i] 
    // for initial configuration.
    $curr_val = 0;
    for ($i = 0; $i < $n; $i++)
        $curr_val += $i * $arr[$i];
  
    // Initialize result
    $res = $curr_val;
  
    // Compute values for
    // other iterations
    for ($i = 1; $i < $n; $i++)
    {
        // Compute next value using 
        // previous value in O(1) time
        $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
$arr = array(8, 3, 1, 2);
$n = sizeof($arr);
echo maxSum($arr, $n);
  
// This code is contributed by ajit
?>

Output:

29

Method 3 (Using pivot: O(n) ):
Below is the implementation using pivot.

C

// C program to find maximum sum of all 
// rotation of i*arr[i] using pivot.
#include<stdio.h>
  
// fun declaration
int maxSum(int arr[], int n); 
int findPivot(int arr[], int n);
  
// function definition
int maxSum(int arr[], int n) 
{
    int sum = 0;
    int i;
    int pivot = findPivot(arr, n);
  
    // difference in pivot and index of 
    // last element of array
    int diff = n - 1 - pivot; 
    for(i = 0; i < n; i++)
    {
        sum= sum + ((i + diff) % n) * arr[i];
    }
    return sum;
}
  
// function to find pivot
int findPivot(int arr[], int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        if(arr[i] > arr[(i + 1) % n])
            return i;
    }
}
  
// Driver code
int main(void)
{
      
    // rotated input array
    int arr[] = {8, 3, 1, 2}; 
    int n = sizeof(arr) / sizeof(int);
    int max = maxSum(arr, n); 
    printf("%d", max);
    return 0; 
}

Java

// Java program to find maximum sum 
// of all rotation of i*arr[i] using pivot.
  
import java.util.*;
import java.lang.*;
import java.io.*;
  
class GFG
{
  
// function definition 
static int maxSum(int arr[], int n) 
{
    int sum = 0;
    int i;
    int pivot = findPivot(arr, n);
  
    // difference in pivot and index of
    // last element of array
    int diff = n - 1 - pivot; 
    for(i = 0; i < n; i++)
    
        sum= sum + ((i + diff) % n) * arr[i];
    }
    return sum;
}
  
// function to find pivot
static int findPivot(int arr[], int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        if(arr[i] > arr[(i + 1) % n])
            return i;
    }
    return 0;
}
  
// Driver code
public static void main(String args[])
{
    // rotated input array
    int arr[] = {8, 3, 1, 2}; 
    int n = arr.length;
    int max = maxSum(arr,n); 
    System.out.println(max);
      
}
}

Python3

# Python3 program to find maximum sum of 
# all rotation of i*arr[i] using pivot. 
  
# function definition 
def maxSum(arr, n) :
  
    sum = 0
    pivot = findPivot(arr, n)
  
    # difference in pivot and index 
    # of last element of array 
    diff = n - 1 - pivot 
    for i in range(n) :
        sum = sum + ((i + diff) % n) * arr[i]; 
      
    return sum
      
# function to find pivot 
def findPivot(arr, n) :
    for i in range(n) : 
  
        if(arr[i] > arr[(i + 1) % n]) :
            return i; 
  
# Driver code 
if __name__ == "__main__" :
  
    # rotated input array 
    arr = [8, 3, 1, 2
    n= len(arr) 
      
    max= maxSum(arr, n)
    print(max)
  
# This code is contributed by Ryuga

C#

// C# program to find maximum sum 
// of all rotation of i*arr[i] using pivot. 
using System;
  
class GFG
{
  
// function definition 
public static int maxSum(int[] arr, int n)
{
    int sum = 0;
    int i;
    int pivot = findPivot(arr,n);
      
    // difference in pivot and index of 
    // last element of array 
    int diff = n - 1 - pivot;
    for (i = 0;i < n;i++)
    {
        sum = sum + ((i + diff) % n) * arr[i];
    }
      
    return sum;
  
}
  
// function to find pivot 
public static int findPivot(int[] arr, int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (arr[i] > arr[(i + 1) % n])
        {
            return i;
        }
    }
    return 0;
    }
  
// Driver code 
public static void Main(string[] args)
{
    // rotated input array 
    int[] arr = new int[] {8, 3, 1, 2};
    int n = arr.Length;
    int max = maxSum(arr,n);
    Console.WriteLine(max);
}
}
  
// This code is contributed by Shrikant13

PHP

<?php
// PHP program to find maximum sum 
// of all rotation of i*arr[i] using pivot.
  
// function definition 
function maxSum($arr, $n
{
$sum = 0;
$pivot = findPivot($arr, $n);
  
// difference in pivot and index of
// last element of array
$diff = $n - 1 - $pivot
for($i = 0; $i < $n; $i++)
{
    $sum = $sum + (($i + $diff) % 
            $n) * $arr[$i];
}
  
return $sum;
  
}
  
// function to find pivot
function findPivot($arr, $n)
{
  
    for($i = 0; $i < $n; $i++)
    {
        if($arr[$i] > $arr[($i + 1) % $n])
        return $i;
    }
    return 0;
}
  
// Driver code
  
// rotated input array
$arr = array(8, 3, 1, 2); 
$n = sizeof($arr);
$max = maxSum($arr, $n); 
echo $max;
  
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>


Output:

29

Time Complexity : O(n)
Auxiliary Space : O(1)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter