Descption of 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.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-function

Chinese version

给定一个长度为 n 的整数数组 nums 。

假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数  F 为：

F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]
返回 F(0), F(1), ..., F(n-1)中的最大值 。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-function

Solution_1

1. generate the array by rotating the nus k positions
2. got all the summarization of F
3. evaluate all the sum values and got its biggest value

codes like following (there are flaws in here.)

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
    
private:
    int max_sum = INT_MIN; // in case the cur_sum
public:
    vector<int> rotate_k_vector(int k, vector<int> nums) {
    
        vector<int> ans;
        // initialize ans by nums 
        ans = nums;
        int n = ans.size();
        if (n == 0) return ans;
        if (k == 0) return ans;
        if (k > n) k = k % n;
        reverse(ans.begin(), ans.begin() + n - k);
        reverse(ans.begin() + n - k, ans.end());
        reverse(ans.begin(), ans.end());
        return ans;
    }
     int maxRotateFunction(vector<int>& nums) {
    
         int n = nums.size();
         int cur_sum = 0;

         for (int i = 0; i < n; i++) {
    
             vector<int> ans = rotate_k_vector(i, nums);
                for (int j = 0; j < n; j++) {
    
                    cur_sum += ans[j] * j;
                }
                max_sum = max(max_sum, cur_sum);
                cur_sum = 0;
         }
            return max_sum;
    }
};
int main() 
{
    
    Solution s;
    vector<int> nums{
    4, 3, 2, 6};
    cout << s.maxRotateFunction(nums) << endl;
    return 0;
}

The flaw is following:

solution_2

Intuition

$F(0)=0\times nums[0]+1\times nums[1]+\cdots +(n-1)\times nums[n-1]$
$F(1)=1\times nums[0]+2\times nums[1]+\cdots +(n\%n)\times nums[n-1]$
$F(1)-F(0)=nums[0]+nums[1]+\cdots +nums[n-2]-(n-1)\times nums[n-1]$
sort it out
$F(1)-F(0)=numSum-nums[n-1]-(n-1)\times nums[n-1]$
$F(1)=F(0)+numSum+n\times nums[n-1]$
abstract the 1 to a
$F(k)=F(k-1)+numSum+n\times nums[n-k]$

The codes for this

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
    
public:
    int maxRotateFunction(vector<int>& nums) {
    
        int sum = 0;
        int len = nums.size();
        int max_sum = INT_MIN;
        int f = 0;
        for (int i = 0; i < len; i++) {
    
            sum += nums[i];
            f += i * nums[i];
        }
        max_sum = f;
        for (int i = len - 1; i >= 0; i--) {
    
            f = f + sum - len * nums[i];
            max_sum = max(max_sum, f);
        }
        return max_sum;
    }
};
int main() 
{
    
    Solution s;
    vector<int> nums{
    4, 3, 2, 6};
    cout << s.maxRotateFunction(nums) << endl;
    return 0;
}

solution_3

intuition
view the $0,1,\cdots ,n-1$ as the transfer variable

The results($O(n^2)$):

The codes :

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
    
public:
    int maxRotateFunction(vector<int>& nums) {
    
        int cur_sum = 0;
        // set max_sum the minimum possible value
        int max_sum = INT_MIN;
        int n = nums.size();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
    
            for (int j = 0; j < n; j++) {
    
                cur_sum += nums[j] * ((j + cnt) % n);
            }
            max_sum = max(max_sum, cur_sum);    
            cur_sum = 0;
            cnt++;
        }
        return max_sum;
    }
};
int main() 
{
    
    Solution s;
    vector<int> nums{
    4, 3, 2, 6};
    cout << s.maxRotateFunction(nums) << endl;
    return 0;
}