Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed - GeeksforGeeks

Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed - GeeksforGeeks

Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed Given an array, only rotation operation is allowed on array. We can rotate the array as many times as we want. Return the maximum possbile of summation of i*arr[i]. Example: Input: arr[] = {1, 20, 2, 10} Output: 72 We can 72 by rotating array twice. {2, 10, 1, 20} 20*3 + 1*2 + 10*1 + 2*0 = 72 Input: arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}; Output: 330 We can 330 by rotating array 9 times. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 0*1 + 1*2 + 2*3 ... 9*10 = 330 We strongly recommend you to minimize your browser and try this yourself first. A Simple Solution is to find all rotations one by one, check sum of every rotation and return the maximum sum. Time complexity of this solution is O(n2). We can solve this problem in O(n) time using an Efficient Solution. Let R j be value of i*arr[i] with j rotations. The idea is to calculate next rotation value from previous rotation, i.e.,

Read full article from Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed - GeeksforGeeks