Maximize Index-Weighted Array Sum When Each Element Swaps at Most Once

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

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

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

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

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.