## Wednesday, July 27, 2016

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

Maximum sum of i*arr[i] among all rotations of a given array - GeeksforGeeks
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.

A simple solution is to try all possible rotations. Compute sum of i*arr[i] for every rotation and return maximum sum.
`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;`
`}`

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 ∑i*arr[i] after one rotation.
curr_val = Current value of ∑i*arr[i]
cum_sum = Sum of all array elements, i.e., ∑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
```
`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;`
`}`
Read full article from Maximum sum of i*arr[i] among all rotations of a given array - GeeksforGeeks