FastPrepSum of Max of Subarrays
Problems/Sum of Max of Subarrays

Sum of Max of Subarrays

Amazon logoAmazon● HardOA

Updated Sep 2026

QuestionFunctionExamples

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 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

Interview reports that mention this question

  • Amazon Full-Time OA Problems, Recent Reports (Part 4 of 5)

Amazon interview experiences

  • Amazon Experienced SDE Onsite Questions: 1 Experience
  • Amazon SDE Onsite Interview Questions: 9 Experiences
  • Amazon SDE II and L5 FDE Interview Questions: 4 Experiences
  • Amazon Full-Time OA Problems, Earlier Reports (Part 5 of 5)
  • Amazon New Grad OA Problems: Every Task We Have (Part 3 of 5)
See Amazon hiring insights
Saved
class Solution {
    public long sumOfMaxOfSubarrays(int[] arr) {
      // write your code here
    }

}
Checking account…