Maximum sum of i * arr [ i ] among all rotations of a given array | An efficient Python3 program to compute maximum sum of i * arr [ i ] ; Compute sum of all array elements ; Compute sum of i * arr [ i ] for initial configuration . ; Initialize result ; Compute values for other iterations ; Compute next value using previous value in O ( 1 ) time ; Update current value ; Update result if required ; Driver code
def maxSum ( arr , n ) : NEW_LINE INDENT cum_sum = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT cum_sum += arr [ i ] NEW_LINE DEDENT curr_val = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT curr_val += i * arr [ i ] NEW_LINE DEDENT res = curr_val NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT next_val = ( curr_val - ( cum_sum - arr [ i - 1 ] ) + arr [ i - 1 ] * ( n - 1 ) ) NEW_LINE curr_val = next_val NEW_LINE res = max ( res , next_val ) NEW_LINE DEDENT return res NEW_LINE DEDENT arr = [ 8 , 3 , 1 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE print ( maxSum ( arr , n ) ) NEW_LINE