Leetcode-396题解

leetcode 396 题解
动态规划，寻找递推公式。

只要找到递推公式就会比较简单。

题目

给定一个长度为 n 的整数数组 nums 。
假设 $arr_k$ 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数 $F$ 为：
$$F(k) = 0 * arr_k[0] + 1 * arr_k[1] + … + (n - 1) * arr_k[n - 1]$$
返回 $F(0), F(1), …, F(n-1)$ 中的最大值 。

生成的测试用例让答案符合 32 位 整数。

示例 1:
输入: nums = [4,3,2,6]
输出: 26
解释:
$$F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 \newline
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16 \newline
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23 \newline
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26$$
所以 $F(0), F(1), F(2), F(3)$ 中的最大值是 $F(3) = 26$ 。

示例 2:
输入: nums = [100]
输出: 0

思路

动态规划

主要是找 F(i) 和 F(i-1) 之间的关系，观察上面的示例1，我们可以看出 F(i) 是通过 F(i-1) + sum(nums) - nums[n-i]*n 得到的，所以有递推关系式
$$F(i) = F(i-1) + \text{sum}(nums) - \text{nums}[n-i] \times n$$

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        long long maximun = 0, n = nums.size(), m = nums.size(), sum = 0, temp = 0, prev = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            maximun += i * nums[i];
            prev += i * nums[i];
        }
        for (int i = 1; i < n; i++) {
            temp = prev + sum - nums[--m] * n;
            prev = temp;
            maximun = max(maximun, temp);
        }
        return maximun;
    }
};