# LeetCode 396: Rotate Function

## Problem Restatement

We are given an integer array `nums` of length `n`.

For each rotation `k`, define `F(k)` as:

```text
F(k) = 0 * arr[k][0] + 1 * arr[k][1] + ... + (n - 1) * arr[k][n - 1]
```

where `arr[k]` is `nums` rotated clockwise by `k` positions.

We need to return the maximum value among:

```text
F(0), F(1), ..., F(n - 1)
```

The answer is guaranteed to fit in a 32-bit signed integer. The constraints are `1 <= n <= 10^5` and `-100 <= nums[i] <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Maximum value of the rotation function |
| Rotation | Clockwise rotation |
| Constraint | `n == nums.length` |
| Constraint | `1 <= n <= 10^5` |
| Constraint | `-100 <= nums[i] <= 100` |

Example function shape:

```python
def maxRotateFunction(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [4, 3, 2, 6]
```

The rotations are:

```text
F(0): [4, 3, 2, 6]
F(1): [6, 4, 3, 2]
F(2): [2, 6, 4, 3]
F(3): [3, 2, 6, 4]
```

Compute each value:

```text
F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 25
F(1) = 0*6 + 1*4 + 2*3 + 3*2 = 16
F(2) = 0*2 + 1*6 + 2*4 + 3*3 = 23
F(3) = 0*3 + 1*2 + 2*6 + 3*4 = 26
```

The maximum is:

```python
26
```

Example 2:

```python
nums = [100]
```

There is only one rotation:

```text
F(0) = 0 * 100 = 0
```

So the answer is:

```python
0
```

## First Thought: Simulate Every Rotation

A direct solution is:

1. Build every rotated array.
2. Compute its rotation function.
3. Track the maximum.

For each rotation, computing `F(k)` costs `O(n)`.

There are `n` rotations.

So the total time is:

```text
O(n^2)
```

With `n` up to `10^5`, this is too slow.

## Key Insight

We can derive `F(k)` from `F(k - 1)` in constant time.

Let:

```python
total = sum(nums)
```

Consider this example:

```python
nums = [4, 3, 2, 6]
```

For `F(0)`:

```text
0*4 + 1*3 + 2*2 + 3*6
```

For `F(1)`, the last element `6` moves to the front:

```text
0*6 + 1*4 + 2*3 + 3*2
```

Every element except the moved element has its multiplier increased by `1`.

Adding `total` increases every multiplier by `1`.

But the moved element was at multiplier `n - 1` and becomes multiplier `0`.

So we subtract `n * moved`.

The recurrence is:

```text
F(k) = F(k - 1) + total - n * nums[n - k]
```

For `k = 1`, the moved element is `nums[n - 1]`.

For `k = 2`, the moved element is `nums[n - 2]`.

And so on.

## Algorithm

First compute:

```python
total = sum(nums)
current = F(0)
```

Then initialize:

```python
best = current
```

For each rotation `k` from `1` to `n - 1`:

1. The moved element is:
   ```python id="4padc8"
   nums[n - k]
   ```
2. Update:
   ```python id="c8lu0h"
   current = current + total - n * nums[n - k]
   ```
3. Update the answer:
   ```python id="o55jfy"
   best = max(best, current)
   ```

Return `best`.

## Correctness

`F(0)` is computed directly from the original array, so it is correct.

For each next rotation, the last element of the previous rotated array moves to the front. Every other element shifts one position to the right, increasing its coefficient by `1`.

Adding `total` to the previous function value accounts for increasing every element's coefficient by `1`.

However, the moved element should not gain one coefficient. It moves from coefficient `n - 1` to coefficient `0`. Adding `total` temporarily gives it coefficient `n`, so subtracting `n * moved` corrects it.

Therefore the recurrence computes each `F(k)` exactly from `F(k - 1)`.

The algorithm computes every rotation value from `F(0)` through `F(n - 1)` and keeps the maximum. Therefore it returns the required maximum rotation function value.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Compute `F(0)`, then update each rotation once |
| Space | `O(1)` | Store only totals and current values |

## Implementation

```python
class Solution:
    def maxRotateFunction(self, nums: list[int]) -> int:
        n = len(nums)

        total = sum(nums)
        current = 0

        for i, num in enumerate(nums):
            current += i * num

        best = current

        for k in range(1, n):
            moved = nums[n - k]
            current = current + total - n * moved
            best = max(best, current)

        return best
```

## Code Explanation

We store the array length:

```python
n = len(nums)
```

Then compute the sum of all values:

```python
total = sum(nums)
```

Now compute `F(0)` directly:

```python
current = 0

for i, num in enumerate(nums):
    current += i * num
```

The first candidate answer is `F(0)`:

```python
best = current
```

Then compute the remaining rotations using the recurrence:

```python
for k in range(1, n):
    moved = nums[n - k]
    current = current + total - n * moved
    best = max(best, current)
```

Finally:

```python
return best
```

## Testing

```python
def test_solution():
    s = Solution()

    assert s.maxRotateFunction([4, 3, 2, 6]) == 26
    assert s.maxRotateFunction([100]) == 0
    assert s.maxRotateFunction([0, 0, 0]) == 0
    assert s.maxRotateFunction([1, 2, 3]) == 8
    assert s.maxRotateFunction([-1, -2, -3]) == -5
    assert s.maxRotateFunction([5, -1, 2]) == 9

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `[4, 3, 2, 6]` | Main example |
| `[100]` | Single element always gives `0` |
| `[0, 0, 0]` | All rotations equal |
| `[1, 2, 3]` | Increasing positive values |
| `[-1, -2, -3]` | Negative values |
| `[5, -1, 2]` | Mixed signs |