How should I practice Maximum Weighted Sum with Disjoint Adjacent Swaps?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Maximum Weighted Sum with Disjoint Adjacent Swaps associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Maximum Weighted Sum with Disjoint Adjacent Swaps

Learn this problem

● Medium

MicrosoftINTERNOA

See Microsoft hiring insights

Problem statement

Given a non-empty integer array arr, you may swap adjacent elements. Each array element may participate in at most one swap, so the chosen adjacent swaps cannot overlap.

After performing any valid set of swaps, define the weighted sum as sum(arr[i] * (i + 1)) over all zero-based indices i.

Return the maximum weighted sum obtainable. The returned value is a signed 64-bit integer.

Function

maxWeightedSum(arr: int[]) → long

Examples

Example 1

arr = [1,3,2]return = 14

Swap the adjacent values 3 and 2 to obtain [1, 2, 3]. Its weighted sum is 1 * 1 + 2 * 2 + 3 * 3 = 14.

Example 2

arr = [4,2,5,1]return = 33

Swap both non-overlapping pairs to obtain [2, 4, 1, 5]. The weighted sum is 2 + 8 + 3 + 20 = 33.

Constraints

1 <= arr.length <= 100000
-1000000000 <= arr[i] <= 1000000000