Coding questions · Reevo

Maximize weighted sum with disjoint adjacent swaps

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.

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.

Maximize Weighted Sum With Disjoint Adjacent Swaps

Choose non-overlapping adjacent swaps to maximize sum arr[i] * (i + 1).

Examples

Example 1

Input: ([1,3,2],)
Output: 14

Explanation: Swapping 3 and 2 gives a positive gain.

Example 2

Input: ([5,1,4,2],)
Output: 33

Explanation: Choose non-overlapping beneficial adjacent swaps.

Hints

Each possible swap has gain arr[i] - arr[i+1].
Run path dynamic programming over non-overlapping edges.