FastPrep
Problem · Array

Sum of Max of Subarrays

Learn this problem
● HardAmazonOA
See Amazon hiring insights

Problem statement

Find the sum of the maximum of all subarrays multiplied by their length in O(n).

For example, given an array arr = [4,2,1,2], the output should be 59.

Function

sumOfMaxOfSubarrays(arr: int[]) → long

Complete the function sumOfMaxOfSubarrays in the editor.

sumOfMaxOfSubarrays has the following parameter:

  1. int[] arr: an array of integers

Returns

long integer: the sum of the maximum of all subarrays multiplied by their length

Examples

Example 1

arr = [4, 2, 1, 2]return = 59
Here's how the sum is calculated: [4] 1 4 1 * 4 = 4 [4, 2] 2 4 2 * 4 = 8 [4, 2, 1] 3 4 3 * 4 = 12 [4, 2, 1, 2] 4 4 4 * 4 = 16 [2] 1 2 1 * 2 = 2 [2, 1] 2 2 2 * 2 = 4 [2, 1, 2] 3 2 3 * 2 = 6 [1] 1 1 1 * 1 = 1 [1, 2] 2 2 2 * 2 = 4 [2] 1 2 1 * 2 = 2 Sum == 59 ☕️

More Amazon problems

drafts saved locally
public long sumOfMaxOfSubarrays(int[] arr) {
  // write your code here
}
arr[4, 2, 1, 2]
expected59
checking account