# 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 + 1*arr +...+ (n-1)*arr[n-1].
After one rotation arr[n-1] is going to be the first element of array,
arr will be the second element and so on.
R(1) = 0*arr[n-1] + 1*arr +...+ (n-1)*arr[n-2].
Therefore,R(1) - R(0) = arr + arr + ... + arr[n-2] - (n-1)*arr[n-1]  =
arr + arr + ... + 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.

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

1. Ritik Bansal says:

rotation array sum
0 2 10 13 1 14 16 43 11 —–> 510
1 10 13 1 14 16 43 11 2 —–> 416
2 13 1 14 16 43 11 2 10 —–> 386
3 1 14 16 43 11 2 10 13 —–> 380
4 14 16 43 11 2 10 13 1 —–> 278
5 16 43 11 2 10 13 1 14 —–> 280
6 43 11 2 10 13 1 14 16 —–> 298
7 11 2 10 13 1 14 16 43 —–> 532
no sum obtained like 686