Maximum Sum of Heights
Reported by candidates from Virtu Financial's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The whole problem hinges on one data structure, a monotonic stack, and Virtu Financial put it in an OA reported in September 2026. You're handed maxHeights, you need a mountain under those caps, and n goes up to 100000. So the brute force of trying every peak and expanding outward dies on time. If you've got an OA coming, learn the stack idea below. StealthCoder sits as a quiet safety net on the live assessment if your mind goes blank, but you can get this one in an evening.
The problem
You are given positive maximum heights maxHeights. Choose a positive height for every index so that height[i] <= maxHeights[i]. The resulting array must be mountain-shaped: for some peak index, heights do not decrease before the peak and do not increase after it. Return the maximum possible sum of the chosen heights. Function maximumSumOfHeights(maxHeights: int[]) → long Examples Example 1 maxHeights = [5,3,4,1,1] return = 13 Choosing [5,3,3,1,1] forms a mountain with sum 13. Example 2 maxHeights = [6,5,3,9,2,7] return = 22 Using index 3 as the peak allows the mountain [3,3,3,9,2,2], whose sum is 22. Constraints 1 <= maxHeights.length <= 100000 1 <= maxHeights[i] <= 10^9
Reported by candidates. Source: FastPrep
Pattern and pitfall
Try every peak, but don't recompute from scratch. Build left[i], the best sum of a non-decreasing run ending at i with height capped at maxHeights[i]. Use a monotonic stack of indices with increasing maxHeights. When you pop bigger values, the previous smaller index j covers the stretch: left[i] = left[j] + maxHeights[i] * (i - j). If the stack is empty, it's maxHeights[i] * (i + 1). Do the same from the right. The answer is the max over i of left[i] + right[i] - maxHeights[i]. The classic pitfalls are overflow, since sums reach about 10^14 so you need a 64-bit type, and double counting the peak. Another is using the wrong comparison, so check equal values against Example 1. If you blank on the live OA, StealthCoder is the hedge that reads the problem and hands you this stack structure, but know the recurrence yourself first.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Maximum Sum of Heights cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Virtu Financial's OA.
Virtu Financial reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Maximum Sum of Heights FAQ
What's the trick in Maximum Sum of Heights?+
Use a monotonic stack to compute, for every index, the best sum if it's the peak on each side. Each height gets clamped to the nearest smaller cap, so a stack lets you reuse earlier results. That drops the O(n^2) peak expansion to O(n).
Will the O(n^2) brute force pass here?+
Not safely. With length up to 100000, expanding left and right from every peak can hit around 10^10 operations in the worst case. It's fine for checking your logic on small cases, but the submitted answer needs the stack approach in linear time.
Why does the answer need a long?+
Heights go up to 10^9 and there can be 100000 of them, so the sum can reach roughly 10^14. A 32-bit int overflows. Use long in Java or C++, and watch intermediate products like maxHeights[i] * (i - j) too.
How do I avoid double counting the peak?+
Your left array and right array both include the peak index at its full cap. When you combine them, compute left[i] + right[i] - maxHeights[i]. Test it on [5,3,4,1,1], where the expected result is 13.
How do I prepare for this in 48 hours?+
Write the next-smaller-element stack from memory first. Then code the left pass, mirror it for the right pass, and combine. Run both examples by hand, then add edge cases: length 1, all equal values, strictly increasing, and strictly decreasing arrays.