Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 396. Rotate Function

---

參考資訊：
https://www.cnblogs.com/fuxuemingzhu/p/15436072.html

題目：


方法：

F(0) = 0A + 1B + 2C +3D
F(1) = 0D + 1A + 2B +3C
F(2) = 0C + 1D + 2A +3B
F(3) = 0B + 1C + 2D +3A

sum = A+B+C+D
F(1) = F(0) + sum - 4D
F(2) = F(1) + sum - 4C
F(3) = F(2) + sum - 4B

F(i) = F(i-1) + sum - n * A[n-i]

解答：

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        long sum = 0;
        long f0 = 0;
        int n = nums.size();

        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            f0 += (i * nums[i]);
        }

        long ans = f0;
        for (int k = 1; k < n; ++k) {
            f0 = f0 + sum - (long)n * nums[n - k];
            ans = max(ans, f0);
        }

        return ans;
    }
};