Maximum score from removing every token in a row, scored by neighbor products
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a row of `n` tokens, where token `i` carries the integer value `nums[i]`. You must remove every token, one at a time, in any order you choose.
Removing a token earns points equal to the product of three values: the removed token's value, the value of the nearest token still remaining to its left, and the value of the nearest token still remaining to its right. If no token remains on one side, that side contributes `1`. Once a token is removed, the tokens on either side of the gap become neighbors.
Return the maximum total number of points you can earn by removing all of the tokens.
### Function Signature
```python
def max_removal_score(nums: list[int]) -> int:
```
### Rules
- Each token is removed exactly once, and the removal order is entirely up to you.
- Removing a token with value `v` whose current left and right neighbors have values `L` and `R` earns `L * v * R`. If no token remains to its left, use `L = 1`; if no token remains to its right, use `R = 1`. These boundary values of `1` are not tokens: they are never removed and earn nothing themselves.
- Neighbors are determined by the row as it stands at the moment of removal, not by the original positions.
- Return the largest total achievable over all removal orders. The answer is a single integer, so it is unique even when several orders reach it.
### Constraints
- `1 <= n <= 300`, where `n == len(nums)`
- `0 <= nums[i] <= 100`
- A single removal earns at most `100 * 100 * 100 = 10^6` points, so the answer is at most `3 * 10^8` and fits in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: nums = [3, 1, 5, 8]
Output: 167
```
One best order: remove `1` (neighbors `3` and `5`, earning `3 * 1 * 5 = 15`), leaving `[3, 5, 8]`; remove `5` (`3 * 5 * 8 = 120`), leaving `[3, 8]`; remove `3` (no left neighbor, so `1 * 3 * 8 = 24`), leaving `[8]`; remove `8` (`1 * 8 * 1 = 8`). The total is `15 + 120 + 24 + 8 = 167`, and no order earns more.
**Example 2**
```text
Input: nums = [2, 3]
Output: 9
```
Removing `2` first earns `1 * 2 * 3 = 6`, then removing `3` earns `1 * 3 * 1 = 3`, for a total of `9`. Removing `3` first earns `2 * 3 * 1 = 6` and then removing `2` earns `1 * 2 * 1 = 2`, for only `8`.
**Example 3**
```text
Input: nums = [5]
Output: 5
```
The only token has no neighbors, so removing it earns `1 * 5 * 1 = 5`.
Overview: Given a row of integers, remove them one at a time in any order; each removal scores the product of the value and its two current neighbors (a missing neighbor counts as 1). Return the maximum possible total score. It tests reasoning about how the removal order changes which values become adjacent and finding an approach far faster than trying every order.
Read the full ByteDance Software Engineer interview experience this question came from
You are given a row of `n` tokens, where token `i` carries the integer value `nums[i]`. You must remove every token, one at a time, in any order you choose.
Removing a token earns points equal to the product of three values: the removed token's value, the value of the nearest token still remaining to its left, and the value of the nearest token still remaining to its right. If no token remains on one side, that side contributes `1`. Once a token is removed, the tokens on either side of the gap become neighbors.
Return the maximum total number of points you can earn by removing all of the tokens.
### Rules
- Each token is removed exactly once, and the removal order is entirely up to you.
- Removing a token with value `v` whose current left and right neighbors have values `L` and `R` earns `L * v * R`. If no token remains to its left, use `L = 1`; if no token remains to its right, use `R = 1`. These boundary values of `1` are not tokens: they are never removed and earn nothing themselves.
- Neighbors are determined by the row as it stands at the moment of removal, not by the original positions.
- Return the largest total achievable over all removal orders. The answer is a single integer, so it is unique even when several orders reach it.
### Constraints
- `1 <= n <= 300`, where `n == len(nums)`
- `0 <= nums[i] <= 100`
- A single removal earns at most `100 * 100 * 100 = 10^6` points, so the answer is at most `3 * 10^8`. It never exceeds `2^31 - 1`, so a signed 32-bit integer result (`int` in Java and C++) is enough.
### Example 1
```text
Input: nums = [3, 1, 5, 8]
Output: 167
```
One best order: remove `1` (neighbors `3` and `5`, earning `3 * 1 * 5 = 15`), leaving `[3, 5, 8]`; remove `5` (`3 * 5 * 8 = 120`), leaving `[3, 8]`; remove `3` (no left neighbor, so `1 * 3 * 8 = 24`), leaving `[8]`; remove `8` (`1 * 8 * 1 = 8`). The total is `15 + 120 + 24 + 8 = 167`, and no order earns more.
### Example 2
```text
Input: nums = [2, 3]
Output: 9
```
Removing `2` first earns `1 * 2 * 3 = 6`, then removing `3` earns `1 * 3 * 1 = 3`, for a total of `9`. Removing `3` first earns `2 * 3 * 1 = 6` and then removing `2` earns `1 * 2 * 1 = 2`, for only `8`.
Constraints
- 1 <= n <= 300, where n == len(nums)
- 0 <= nums[i] <= 100
- A single removal earns at most 100 * 100 * 100 = 10^6 points, so the answer is at most 3 * 10^8 and fits in a signed 32-bit integer (it never exceeds 2^31 - 1)
Examples
Input: ([3, 1, 5, 8],)
Expected Output: 167
Explanation: Source example 1: remove 1 (15), 5 (120), 3 (24), then 8 (8) for 167; greedy rules such as smallest first fall short.
Input: ([2, 3],)
Expected Output: 9
Explanation: Source example 2: two tokens; removing 2 first gives 6 + 3 = 9, removing 3 first only 6 + 2 = 8.
Hints
- The boundary 1s are never removed, so you can picture the row with a permanent 1 at each end.
- Try several orders on [3, 1, 5, 8] by hand: simple rules such as removing the smallest token first, or saving the largest for last, do not always reach the maximum.
- While two tokens both remain, the removals strictly between them never see anything outside those two. Ask how that lets you split the row into independent parts.