FastPrep
Problem · Array

Get Maximum Sum of Strengths

Learn this problem
● MediumSalesforceFULLTIMEOA
See Salesforce hiring insights

Problem statement

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 where 0 ≤ i < n - 1 and swap arr[i] with arr[i + 1]. Each element of the array can be swapped at most once during the whole process.

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

Function

getMaximumSumOfStrengths(arr: int[]) → long

Complete the function getMaximumSumOfStrengths in the editor below.

getMaximumSumOfStrengths has the following parameter:

  1. int arr[n]: the initial array

Returns

long int: the maximum sum of strengths

Examples

Example 1

arr = [1, 9, 7, 3, 2]return = 66

It is optimal to swap (arr[2], arr[3]). The final array is arr[] = [1, 9, 3, 7, 2]. The sum of strengths (1*1 + 2*9 + 3*3 + 4*7 + 5*2) = 66, which is the maximum possible.

Example 2

arr = [2, 1, 4, 3]return = 30

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

Example 3

arr = [1, 2, 5]return = 20

No swaps are needed as the array is already in optimal order. The sum of strengths (1*1 + 2*2 + 3*5) = 20, which is the maximum possible.

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^5

    • More Salesforce problems

    drafts saved locally
    public long getMaximumSumOfStrengths(int[] arr) {
 // write your code here
}
    arr[1, 9, 7, 3, 2]
    expected66
    checking account