396.旋转函数

链接：396.旋转函数
难度：Medium
标签：数组、数学、动态规划
简介：返回 F(0), F(1), ..., F(n-1)中的最大值 。

题解 1 - cpp

• 编辑时间：2022-04-22
• 执行用时：140ms
• 内存消耗：93.6MB
• 编程语言：cpp
• 解法介绍：每一次的值可以从上一次推导过来 f(n) = f(n-1) + sum - n * nums[i]。

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