A hillside vineyard is laid out as a single line of terraces running down the slope, each terrace planted with a batch of vines and monitored for a yield index. A vintner wants to pick three terraces at strictly increasing positions along the line — an early terrace i, a middle terrace j, and a late terrace k, with i < j < k — and measure a contrast score equal to (yield of terrace i minus yield of terrace j) multiplied by the yield of terrace k. The vintner wants the highest contrast score achievable from any such triplet of terraces; if every valid triplet gives a score of zero or less, the answer is 0.
The first line contains a single integer n, the number of terraces. The second line contains n space-separated integers yield[0], yield[1], ..., yield[n-1], the yield index of each terrace in left-to-right order.
Print a single integer: the maximum value of (yield[i] - yield[j]) * yield[k] over all triplets of indices with i < j < k, or 0 if no triplet gives a positive value.
Example 1
Input
5 12 6 1 2 7
Expected
77
Explanation
Terraces have yields [12, 6, 1, 2, 7]. Choosing i=0 (yield 12), j=2 (yield 1), and k=4 (yield 7) gives (12 - 1) * 7 = 77, which is the best score among all valid triplets, so the answer is 77.
Example 2
Input
4 1 2 3 4
Expected
0
Explanation
Yields [1, 2, 3, 4] are non-decreasing left to right, so for every triplet i<j<k we have yield[i] <= yield[j], making (yield[i]-yield[j]) <= 0 and every triplet's score at most 0. The answer is therefore 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →