# Java program to find maximum value of sum of all (i*arr[i]) with only rotations allowed in the array

Hi coders! In this tutorial, we are going to discuss a problem that is related to rotation in an array. Many of you have definitely solved the problem of array rotation but the problem which I am going to discuss is a bit tricky. So let’s start learning how to find maximum value of sum of all (i*arr[i]) with only rotations allowed in the array in Java.

## Find maximum value of sum of all (i*arr[i]) with only rotations allowed in the array in Java

The problem is like: Suppose we have given an array of integers i.e arr: [2, 10, 13, 1, 14, 16, 43, 11], we have to find the maximum value of the sum of all (i*arr[i]). (i represents the index of the array).

A naive approach to solve this is to simply find the sum for every rotation and compare all sums but this is going to be done in O(n^2) time complexity.

Here comes an efficient solution for this problem which can reduce the time complexity from O(n^2) to O(n).

The idea is to find the next rotation value from the previous rotation value i.e if R(i) = i*arr[i] then R(i+1) can be calculated from R(i).

### Mathematical justification

Calculate the initial value of i*arr[i] with no rotation R(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1]. After one rotation arr[n-1] is going to be the first element of array, arr[0] will be the second element and so on. R(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2]. Therefore,R(1) - R(0) = arr[0] + arr[1] + ... + arr[n-2] - (n-1)*arr[n-1] = arr[0] + arr[1] + ... + arr[n-3] - (n-1)*arr[n-2] + arr[n-1] If we look at the above values, we can observe R(i)-R(i-1)= arrSum - n * arr[n-j]. Note: arrSum is the sum of all elements of the array.

### Java program to find maximum value of sum of all (i*arr[i]) with only rotations allowed in the array

import java.util.*; public class RotationMaxSum { private static int maxSum(int[] arr) { /* function that calculates maximum sum and return it */ int n = arr.length; int arrSum = 0; int current = 0; for(int i = 0; i < n; i++) { arrSum = arrSum + arr[i]; current = current + i*arr[i]; } int maxVal = current; for(int i = 0; i < n;i++) { current = current + arrSum - n*arr[n - 1]; if(current > maxVal) { maxVal = current; } } return maxVal; } /* driver function */ public static void main(String[] args) { int[] arr = { 2, 10, 13, 1, 14, 16, 43, 11}; /* given array */ System.out.println("Maximum sum after possible rotations is: "+ maxSum(arr)); } } // Code is provided by Anubhav Srivastava

The above given code gives the output as:

Output Maximum sum after possible rotations is: 686

Hence, the time complexity of the above code is **O(n) **and the space complexity is **O(1).**

I hope you like the solution.

## Leave a Reply