Sum of Max of Subarrays
Updated
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:
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 = 59Here'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 interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Most Segments That Sort the ArrayRippling · OARippling interview questions
- Maximum Sum of HeightsVirtu Financial · OAVirtu Financial interview questions
- Trapping Rain WaterGoogle · OAGoogle interview questions
- Alternating Jumps to the Last IndexExpedia · OAExpedia interview questions
- Pipe Removal TurnsWells Fargo · OAWells Fargo interview questions
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Sum of Subarray MinimumsNVIDIA · OANVIDIA interview questions
- Shopkeeper Final Price SummaryMicrosoft · OAMicrosoft interview questions
- Nested Recipe Blocks (Game Adaptation)Roblox · OARoblox interview questions
- Maximum Capped Histogram Area After One RemovalMyntra · OAMyntra interview questions