Find maximum value of sum of index element products(i*array[i]) with only rotations allowed on a given array

http://www.ideserve.co.in/learn/maximum-value-of-index-element-product-sum-with-only-rotations
Given an array, find the maximum possible value of sum of index-element-products(i*array[i]) with only rotations allowed on a given array. Sum of index-element-products for array of length 'n' is computed as - 0*array[0] + 1*array[1] + 2*array[2] + ... + n-1*array[n-1].

For example, for the array {3,4,5,6,1,2} without doing any rotations sum of index-element-products is 46. After doing one clockwise rotation of the array, it would be modified to {2,3,4,5,6,1} and sum of index-element-products in this case is 55.
As you should be able to confirm, maximum value of sum of index-element-products for this given array is 70 which is obtained after performing two clockwise rotations in which case modified array is {1,2,3,4,5,6}.

For the array {24,26,25,22}, 

index-element-products sum without any rotation is 142. The maximum sum of index-element-products that could be obtained is 151 which is obtained with one clockwise rotation(modified array {22,24,26,25}).

Simple approach: If 'n' is the length of given array and if we perform all the 'n' possible clockwise rotations then we can compute all possible values of sum of index-element-products to find out maximum possible sum. Since computing sum of index-element-products for an array takes O(n) time, overall time complexity of this approach is O(n^2). You can check function 'simpleFindMaxIndexElementProductSum(int[] array)' in following code snippet for implementation details..

Optimized approach: Without doing any rotations on the given 'array', sum of index-element-products is -
0*array[0] + 1*array[1] + 2*array[2] + .... + (n-2)*array[n-2] + (n-1)*array[n-1]. Let's call this sum as 'sum_0'

After performing one clockwise rotation, sum of index-element-products would be -
0*array[n-1] + 1*array[0] + 2*array[1] + .... + (n-2)*array[n-3] + (n-1)*array[n-2]. Let's call this sum as 'sum_1'.

After performing two clockwise rotations, sum of index-element-products would be -
0*array[n-2] + 1*array[n-1] + 2*array[0] + .... + (n-2)*array[n-4] + (n-1)*array[n-3]. Let's call this sum as 'sum_2'.

Now the value of 'sum_1' - 'sum_0' is (array[0] + array[1] + .. array[n-2]) - (n-1)*array[n-1] which is equal to (array[0] + array[1] + .. array[n-2] + array[n-1]) - n*array[n-1].
Similarly, value of 'sum_2' - 'sum_1' is (array[0] + array[1] + .. array[n-2] + array[n-1]) - n*array[n-2]

Using the same analogy above, given 'sum_(i-1)'(sum after 'i-1' clockwise rotations) we can compute 'sum_i' by using
sum_i = sum_(i-1) + sum of all array elements - n*(array[n-i]).

If we use this mathematical approach, we need to iterate over all the array elements only once to compute 'sum_0' and sum of all array elements. Using these values and above mathematical relation, we can then compute values of sum of index-element-products for all the 'n' possible clockwise rotations of given array and find out the maximum sum possible in O(n) time. Therefore, overall time complexity of this approach is O(n) with O(1) space complexity. In the code snippet below, you can check the function 'findMaxIndexElementProductSum(int[] array)' for implementation details.

    private int findIndexElementProductSum(int[] array)

    {

        int currValue = 0;

        for (int i = 0; i < array.length; i++)

        {

            currValue   += i*array[i];

        }

         

        return currValue;

    }

     

    private void rotateClockwise(int[] array)

    {

        if (array == null || array.length < 2)

        {

            return;

        }

         

        int n = array.length;

        int temp = array[n-1];

         

        for (int i = n-1; i >= 1; i--)

        {

            array[i] = array[i-1];

        }

        array[0] = temp;

    }

     

     

    public int simpleFindMaxIndexElementProductSum(int[] array)

    {

        // currValue indicates index-element-product sum when no rotation is performed

        int sumElements = 0, currValue = 0;

        for (int i = 0; i < array.length; i++)

        {

            sumElements += array[i];

            currValue   += i*array[i];

        }

 

 

        int maxValue = currValue, n = array.length;

         

        for (int i = 1; i < n; i++)

        {

            rotateClockwise(array);

            currValue = findIndexElementProductSum(array);

            if (currValue > maxValue)

            {

                maxValue = currValue;

            }

        }

         

        return maxValue;

    }

 

    public int findMaxIndexElementProductSum(int[] array)

    {

        // currValue indicates index-element-product sum when no rotation is performed

        int sumElements = 0, currValue = 0;

        for (int i = 0; i < array.length; i++)

        {

            sumElements += array[i];

            currValue   += i*array[i];

        }

 

        /*

         * If 'n' indicates length of array then there could be maximum 'n-1' rotations.

         * n'th rotation restores the original array.

         *

         * If 'currValue' is the index-element-product sum after 'i-1' rotations then

         * the index-element-product sum after 'i' rotations would be currValue + sumElements - n*array[n-i]

         */

        int maxValue = currValue, n = array.length;

         

        for (int i = 1; i < n; i++)

        {

            currValue += sumElements - n*array[n-i];

            if (currValue > maxValue)

            {

                maxValue = currValue;

            }

        }

         

        return maxValue;

    }