Maximize weighted sum with disjoint adjacent swaps
Company: Reevo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an integer array `arr` of length `n` (0-indexed).
Define the weighted sum as:
`S = Σ_{i=0..n-1} arr[i] * (i + 1)`.
You may perform any number of **adjacent swaps** of the form swap `arr[i]` and `arr[i+1]`, with the constraint that **each array position can be involved in at most one swap** (i.e., chosen swaps must be **non-overlapping**).
Return the **maximum possible** value of `S` after performing such swaps.
Constraints (typical for this OA style): `1 ≤ n ≤ 2e5`, `|arr[i]|` fits in 32-bit signed integer. Output may require 64-bit integer.
Quick Answer: This question evaluates a candidate's competency in array manipulation, combinatorial optimization, and algorithmic reasoning about how local adjacent swaps affect a weighted global objective.
Choose non-overlapping adjacent swaps to maximize sum arr[i] * (i + 1).
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,3,2],)
Expected Output: 14
Explanation: Swapping 3 and 2 gives a positive gain.
Input: ([5,1,4,2],)
Expected Output: 33
Explanation: Choose non-overlapping beneficial adjacent swaps.
Input: ([1,2,3],)
Expected Output: 14
Explanation: No positive-gain swap is useful.
Input: ([7],)
Expected Output: 7
Explanation: A single element cannot be swapped.
Hints
- Each possible swap has gain arr[i] - arr[i+1].
- Run path dynamic programming over non-overlapping edges.