FastPrepFastPrep
Problem Brief

Element Swapping

OA

A software development firm is hiring engineers and used the following challenge in its online test.

Given an array arr that contains n integers, the following operation can be performed on it any number of times (possibly zero):

  • - Choose any index i (0 ≤ i and swap arr[i] and arr[i + 1]
  • - Each element of the array can be swapped at most once during the whole process.

    • The strength of an index i is defined as arr[i] * (i + 1) using 0-based indexing. Find the maximum possible sum of the strengths of all indices after optimal swaps. Mathematically, maximize the following:

    Function Description

    Complete the function getMaximumSumOfStrengths in the editor below.

    getMaximumSumOfStrengths has the following parameter:

    • int arr[n]: the initial array

    Returns

    long integer: the maximum possible sum of strengths of all indices after the operations are applied optimally

    1Example 1

    Input
    arr = [2, 1, 4, 3]
    Output
    30
    Explanation
    It is optimal to swap (arr[2], arr[3]) and (arr[0], arr[1]). The final array is [1, 2, 3, 4], and the sum of strengths = (1 * 1 + 2 * 2 + 3 * 3 + 4 * 4) = 30, which is maximum possible. Thus, the answer is 30.

    Constraints

    Limits and guarantees your solution can rely on.

    • 1 ≤ n ≤ 10^5
    • 1 ≤ arr[i] ≤ 10^5
    public long getMaximumSumOfStrengths(int[] arr) {
  // write your code here
}
    Input

    arr

    [2, 1, 4, 3]

    Output

    30

    Sign in to submit your solution.