LeetCode 396 Rotate Function 思维

You are given an integer array nums of length n.

Assume \(arr_k\) 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 * arr_k[0] + 1 * arr_k[1] + ... + (n - 1) * arr_k[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.

Solution

假设 \(nums = [a,b,c,d], s = a+b+c+d\)，对于 \(F(0):\)

对于 \(F(1):\)

所以：

其他也是同理。因此我们只需要递推即可求解所有的 \(F()\)， 复杂度 \(O(n)\)

class Solution {
private:
    int ans = 0;
public:
    int maxRotateFunction(vector& nums) {
        int s = 0, n = nums.size();
        for(int i=0;i