values of length n. Its *weighted sum* is 0·a[0] + 1·a[1] + … + (n − 1)·a[n − 1]: every element is multiplied by its index.
The array can be rotated by any number of positions (the last element wraps around to the front). Find the largest weighted sum over all n rotations of values, the original array included.
Trying every rotation takes O(n²); aim for O(n).values=[2, 0, 5] → 10
The rotations are [2, 0, 5] giving 0·2 + 1·0 + 2·5 = 10, [5, 2, 0] giving 2 and [0, 5, 2] giving 9. The maximum is 10.
values=[-3, 7] → 7
[-3, 7] gives 7 and [7, -3] gives -3.
values=[42] → 0
The only element sits at position 0 and is multiplied by zero.
values=[2, 0, 5]
10
Run checks the first 3 tests in your browser. Submit checks all 83 tests on the server, hidden ones included.