Rotate Function Problem


Description

LeetCode Problem 396.

You are given an integer array nums of length n.

Assume arr_k 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 * arr_k[0] + 1 * arr_k[1] + … + (n - 1) * arr_k[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.

Example 1:

1
2
3
4
5
6
7
8
Input: nums = [4,3,2,6]
Output: 26
Explanation:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Example 2:

1
2
Input: nums = [100]
Output: 0

Constraints:

  • n == nums.length
  • 1 <= n <= 10^5
  • -100 <= nums[i] <= 100


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        int F = 0, sum = 0, n = A.size();
        for (int i = 0; i < n; ++i){
            F += i * A[i];
            sum += A[i];
        }
        int m = F;
        for (int i = n - 1; i >= 0; --i){
            F = F + sum - n * A[i];
            m = max(m, F);
        }
        return m;
    }
};




Related Posts

1-Bit And 2-Bit Characters Problem

LeetCode 717. We have two special characters, the first character...

Teemo Attacking Problem

LeetCode 495. Our hero Teemo is attacking an enemy Ashe...

Range Addition II Problem

LeetCode 598. You are given an m x n matrix...

Max Consecutive Ones Problem

LeetCode 485. Given a binary array nums, return the maximum...

132 Pattern Problem

LeetCode 456. Given an arrayof n integers nums, a 132...

Summary Ranges Problem

LeetCode 228. You are given a sorted unique integer array...