C++ Solution


  • 0
    //遞推公式乃 F(k) = F(k - 1) + S - n * B_{k - 1}(n - 1) 
    //               = F(k - 1) + S - n * B_{0}(n - k)
    //這裡B_{k}(i) = B_{0}((i - k) % n), S是所有A[i], i = 0, 1, ..., n - 1之和。
    
    class Solution {
    public:
    	int maxRotateFunction(vector<int>& A) {
    		int n = A.size();
    		if (n == 0) return 0;
    		if (n == 1) return 0;
    		int max_sum = INT_MIN;
    		int sum = 0;
    		for (int i = 0; i < n; ++i) {
    			sum += A[i];
    		}
    		int F = 0;
    		for (int j = 0; j < n; ++j) {
    			F += j * A[j];
    		}
    		max_sum = max(max_sum, F);
    		for (int k = 1; k < n; ++k) {
    			F += sum - n * A[n - k];
    			max_sum = max(max_sum, F);
    		}
    		return max_sum;
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.