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.

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:

   March 27, 2020 at 11:30 am

   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

   Reply