Amazon OA question

Round 1

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

Eg. arr = [4,2,1,2]
Output : 59

• [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.