Maximize Index-Weighted Array Sum When Each Element Swaps at Most Once
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are given an integer array `nums`. You may swap elements, choosing any two positions for each swap, but every element may take part in at most one swap. After the swaps, the score of the array is the sum of `nums[i] * i` over all positions `i`. Return the maximum score you can reach.
### Function Signature
```python
def max_index_weighted_sum(nums: list[int]) -> int:
```
### Rules
- Positions are 0-indexed, so the score is `0 * nums[0] + 1 * nums[1] + ... + (n - 1) * nums[n - 1]`, computed on the array after all swaps.
- A swap exchanges the elements at two different positions. The two positions do not have to be adjacent.
- Each element takes part in at most one swap, so the swaps you choose use pairwise disjoint pairs of positions, and their order does not matter. Making no swap at all is allowed.
- Return the maximum score as an integer.
### Constraints
- `1 <= len(nums) <= 16`
- `0 <= nums[i] <= 10^6`
- The answer is at most `1.2 * 10^8`, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: nums = [2, 1, 4, 3]
Output: 20
```
Swapping positions 0 and 1, and positions 2 and 3, gives `[1, 2, 3, 4]` with score `0 + 2 + 6 + 12 = 20`. No arrangement of these values scores more.
**Example 2**
```text
Input: nums = [3, 1, 2]
Output: 7
```
The sorted arrangement `[1, 2, 3]` would score 8, but reaching it moves all three elements around a cycle, which needs two swaps that share an element. Swapping positions 0 and 1 gives `[1, 3, 2]` with score `0 + 3 + 4 = 7`; swapping positions 0 and 2 gives `[2, 1, 3]`, also 7.
**Example 3**
```text
Input: nums = [3, 4, 1, 2]
Output: 20
```
The original score is `0 + 4 + 2 + 6 = 12`. Swapping positions 0 and 2, and positions 1 and 3, gives `[1, 2, 3, 4]` with score 20.
Overview: An array optimization problem: maximize the sum of each element times its index when any two elements may be swapped but every element can take part in at most one swap. It tests modeling the at-most-once rule precisely and finding the best set of disjoint swaps within small input limits.
Read the full Visa Software Engineer interview experience this question came from
You are given an integer array `nums` of length `n`. You may swap elements: each swap exchanges the elements at two different positions, and the two positions do not have to be adjacent. Every element may take part in at most one swap, so the swaps you choose use pairwise disjoint pairs of positions and their order does not matter. Making no swap at all is allowed.
After the swaps, the score of the array is the sum of `nums[i] * i` over all positions `i`. Positions are 0-indexed, so the score is `0 * nums[0] + 1 * nums[1] + ... + (n - 1) * nums[n - 1]`, computed on the array after all swaps.
Return the maximum score you can reach, as an integer.
### Constraints
- `1 <= len(nums) <= 16`
- `0 <= nums[i] <= 10^6`
- The answer is at most `1.2 * 10^8`, so it fits in a 32-bit signed integer. No value, including the answer, exceeds `2^31 - 1`, so Java and C++ use `int`.
### Examples
**Example 1**
```text
Input: nums = [2, 1, 4, 3]
Output: 20
```
Swapping positions 0 and 1, and positions 2 and 3, gives `[1, 2, 3, 4]` with score `0 + 2 + 6 + 12 = 20`. No arrangement of these values scores more.
**Example 2**
```text
Input: nums = [3, 1, 2]
Output: 7
```
The sorted arrangement `[1, 2, 3]` would score 8, but reaching it moves all three elements around a cycle, which needs two swaps that share an element. Swapping positions 0 and 1 gives `[1, 3, 2]` with score `0 + 3 + 4 = 7`; swapping positions 0 and 2 gives `[2, 1, 3]`, also 7.
Constraints
- 1 <= len(nums) <= 16
- 0 <= nums[i] <= 10^6
- The answer is at most 1.2 * 10^8, so it fits in a 32-bit signed integer.
Examples
Input: ([1000000],)
Expected Output: 0
Explanation: Singleton at the value bound: position 0 has weight 0 and no swap is possible, so the score is 0.
Input: ([1, 2],)
Expected Output: 2
Explanation: Length 2 already in order: swapping would drop the score to 1, so make no swap; score 2.
Hints
- Work out how one swap of positions i < j changes the score. The change depends only on the two values and on the distance j - i, and swaps on disjoint positions do not affect each other's change.
- Sorting ascending gives an upper bound on the score, but Example 2 shows it is not always reachable when each element may join at most one swap.
- The array has at most 16 positions, so comparing many different collections of non-overlapping swaps is affordable.