# 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 ` ` `  `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

## 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

 ` `

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 ` ` `  `using` `namespace` `std; ` ` `  `int` `maxSum(``int` `arr[], ``int` `n) ` `{ ` `    ``// Compute sum of all array elements ` `    ``int` `cum_sum = 0; ` `    ``for` `(``int` `i=0; i

## 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

 ` `

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 ` ` `  `// 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

 ` ``\$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)

## tags:

Arrays Amazon rotation Amazon Arrays

code