problem

You are given an integer array nums of length n.

Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:

  • F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].

Return the maximum value of F(0), F(1), ..., F(n-1).

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

Input: nums = [4,3,2,6]
Output: 26
Explanation:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Example 2:

Input: nums = [100]
Output: 0

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • -100 <= nums[i] <= 100

submission

// the most naive solution would be simulate
// for i in 0..n: rotate the vec and sum the F(i)
// the time complexity of which is O(n^2)
// however we can optimize this with DP
// F(k) = 0*A_k[0] + 1*A_k[1] + ... + (n-1)*A_k[n-1]
// F(k-1) = 0*A_k-1[0] + 1*A_k-1[1] + ... + (n-1)*A_k-1[n-1]
// from the rotation, we can derive:
// F(k) - F(k-1) = S - n*A_k-1[n-1]
// with S = sum(arr), n = len(arr)
impl Solution {
    pub fn max_rotate_function(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let sum: i32 = nums.iter().sum();
        // init F(0)
        let f0: i32 = nums.iter()
            .enumerate()
            .map(|(idx, &val)| idx as i32 * val)
            .sum();
        nums.into_iter()
            .rev() // notice the rev here
            .fold((f0, f0), |(max, cur), val| {
                // update max F and cur F
                (max.max(cur), sum + cur - n * val)
            })
            .0
    }
}