# Rotate Function
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rotate-function)
Canonical: https://scaleengineer.com/dsa/problems/rotate-function
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## 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.

**Example 1:**

**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:**

**Input:** nums = [100]
**Output:** 0

**Constraints:**

* `n == nums.length`
* `1 <= n <= 105`
* `-100 <= nums[i] <= 100`

# Approaches
## Brute Force by Simulating Rotations
This approach directly follows the problem definition. It iterates through all possible `n` rotations. For each rotation `k`, it first constructs the rotated array `arr_k` and then computes the rotation function `F(k)` by summing the products `i * arr_k[i]`. The maximum value found among all `F(k)` is the result.
**Time:** O(n^2) - The outer loop runs `n` times for each rotation. Inside, creating the rotated array takes `O(n)` time, and calculating `F(k)` also takes `O(n)` time. Thus, the total complexity is `n * (O(n) + O(n)) = O(n^2)`. · **Space:** O(n) - In each iteration of the outer loop, a new array of size `n` is created to store the rotated version of `nums`.
**Pros:** Simple to understand and implement.; Directly translates the problem statement into code.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.; With `n` up to `10^5`, an `O(n^2)` solution will result in a 'Time Limit Exceeded' error.
### Explanation
The core idea is to simulate the process described in the problem. We generate each of the `n` possible rotated arrays and calculate the rotation function for each one, keeping track of the maximum value.

**Algorithm:**

*   Initialize `maxF` to the smallest possible integer value.
*   Loop for `k` from `0` to `n-1`:
    *   Create a temporary array `rotatedNums` of size `n`.
    *   Populate `rotatedNums` by simulating the rotation: for each `i` from `0` to `n-1`, set `rotatedNums[(i + k) % n] = nums[i]`.
    *   Initialize `currentF = 0`.
    *   Calculate `F(k)`: for each `j` from `0` to `n-1`, add `j * rotatedNums[j]` to `currentF`.
    *   Update `maxF = Math.max(maxF, currentF)`.
*   Return `maxF`.

```java
class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }
        int maxF = Integer.MIN_VALUE;

        for (int k = 0; k < n; k++) {
            // 1. Create the rotated array for rotation k
            int[] rotatedNums = new int[n];
            for (int i = 0; i < n; i++) {
                rotatedNums[(i + k) % n] = nums[i];
            }

            // 2. Calculate F(k) for the rotated array
            int currentF = 0;
            for (int i = 0; i < n; i++) {
                currentF += i * rotatedNums[i];
            }
            
            // 3. Update the maximum
            maxF = Math.max(maxF, currentF);
        }
        return maxF;
    }
}
```
### Algorithm
*   Initialize `maxF` to the smallest possible integer value.
*   Loop for `k` from `0` to `n-1`:
    *   Create a temporary array `rotatedNums` of size `n`.
    *   Populate `rotatedNums` by simulating the rotation: for each `i` from `0` to `n-1`, set `rotatedNums[(i + k) % n] = nums[i]`.
    *   Initialize `currentF = 0`.
    *   Calculate `F(k)`: for each `j` from `0` to `n-1`, add `j * rotatedNums[j]` to `currentF`.
    *   Update `maxF = Math.max(maxF, currentF)`.
*   Return `maxF`.

## Optimized Approach with Mathematical Derivation
Instead of re-calculating the entire sum for each rotation, this approach finds a mathematical relationship between `F(k)` and `F(k-1)`. By observing how the function value changes from one rotation to the next, we can compute `F(k)` from `F(k-1)` in constant time. This dramatically reduces the overall time complexity.
**Time:** O(n) - We perform a single pass to calculate the initial sum and `F(0)`, which takes `O(n)`. Then, we loop `n-1` times, with each step taking `O(1)` time. The total time complexity is `O(n)`. · **Space:** O(1) - We only use a few variables to store the current sum, the total sum, and the maximum value, regardless of the input size.
**Pros:** Highly efficient, with linear time complexity.; Minimal space usage.; Optimal solution for the given constraints.
**Cons:** Requires mathematical insight to derive the recurrence relation, making it less obvious than the brute-force approach.
### Explanation
This method avoids the expensive re-computation in the brute-force approach by deriving a recurrence relation. Let `S` be the sum of all elements in `nums`.

Let's compare `F(k)` and `F(k-1)`. The array for `F(k)` is the array for `F(k-1)` rotated by one position. After some algebraic manipulation, we can derive the recurrence relation: `F(k) = F(k-1) + S - n * (last element of the array for F(k-1))`.

The last element of the array for `F(k-1)` (which is `nums` rotated `k-1` times) corresponds to the element `nums[n-k]` in the original array. So, the final formula is `F(k) = F(k-1) + S - n * nums[n-k]`.

**Algorithm:**

*   Calculate the sum of all elements, `arraySum`.
*   Calculate the initial function value `F(0)`.
*   Initialize `maxF` with the value of `F(0)`.
*   Iterate `k` from `1` to `n-1`:
    *   Calculate the next function value `F(k)` using the formula: `currentF = currentF + arraySum - n * nums[n-k]`.
    *   Update `maxF = Math.max(maxF, currentF)`.
*   Return `maxF`.

**Note:** Intermediate sums can exceed the 32-bit integer limit. Use 64-bit integers (`long` in Java) for calculations involving `F(k)` and `arraySum`.

```java
class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        long arraySum = 0;
        long currentF = 0;
        for (int i = 0; i < n; i++) {
            arraySum += nums[i];
            currentF += (long) i * nums[i];
        }

        long maxF = currentF;

        for (int k = 1; k < n; k++) {
            // F(k) = F(k-1) + arraySum - n * nums[n-k]
            currentF = currentF + arraySum - (long) n * nums[n - k];
            maxF = Math.max(maxF, currentF);
        }

        return (int) maxF;
    }
}
```
### Algorithm
*   Calculate the sum of all elements, `arraySum`.
*   Calculate the initial function value `F(0)`.
*   Initialize `maxF` with the value of `F(0)`.
*   Iterate `k` from `1` to `n-1`:
    *   Calculate the next function value `F(k)` using the formula: `currentF = currentF + arraySum - n * nums[n-k]`.
    *   Update `maxF = Math.max(maxF, currentF)`.
*   Return `maxF`.

# Solutions
### Java

```java
public class Rotate_Function { class Solution { public int maxRotateFunction ( int [] A ) { int prevValue = 0 ; int sum = 0 ; int n = A . length ; for ( int i = 0 ; i < n ; ++ i ) { sum += A [ i ]; // get: 1A+1B+1C+1D+... prevValue += i * A [ i ]; // get: F(0) first } int result = prevValue ; for ( int i = 1 ; i < n ; i ++) { // start from index=1 prevValue = prevValue + sum - n * A [ n - i ]; result = Math . max ( result , prevValue ); } return result ; } } } ############ class Solution { public int maxRotateFunction ( int [] nums ) { int f = 0 ; int s = 0 ; int n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { f += i * nums [ i ]; s += nums [ i ]; } int ans = f ; for ( int i = 1 ; i < n ; ++ i ) { f = f + s - n * nums [ n - i ]; ans = Math . max ( ans , f ); } return ans ; } }
```

### Python

```python
class Solution : def maxRotateFunction ( self , nums : List [ int ]) -> int : f = sum ( i * v for i , v in enumerate ( nums )) n , s = len ( nums ), sum ( nums ) ans = f for i in range ( 1 , n ): # starting at 1, not 0 which is f f = f + s - n * nums [ n - i ] ans = max ( ans , f ) return ans ############ class Solution ( object ): def maxRotateFunction ( self , A ): """ :type A: List[int] :rtype: int """ if not A : return 0 sumA = sum ( A ) fk = 0 n = len ( A ) for i , num in enumerate ( A ): fk += i * num idx = n - 1 ans = float ( "-inf" ) for _ in range ( n ): fk += sumA - n * A [ idx ] ans = max ( ans , fk ) idx -= 1 return ans
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/rotate-function/ // Time: O(N) // Space: O(1) class Solution { public: int maxRotateFunction ( vector < int >& A ) { if ( A . empty ()) return 0 ; long long f = 0 , ans = INT_MIN , N = A . size (), sum = accumulate ( A . begin (), A . end (), ( long long ) 0 ); for ( int i = 0 ; i < N ; ++ i ) f += i * A [ i ]; for ( int i = N - 1 ; i >= 0 ; -- i ) ans = max ( ans , f += ( sum - N * A [ i ])); return ans ; } };
```