Maximize the Value of an Ordered Index Triplet

# Maximize the Value of an Ordered Index Triplet You are given a 0-indexed integer array `nums`. For three indices satisfying `i < j < k`, their triplet value is `(nums[i] - nums[j]) * nums[k]`. Return the largest value over all such ordered index triplets. If every triplet value is negative, return `0`. ### Examples **Example 1** ```text Input: nums = [9,2,8,3] Output: 56 ``` The triplet `(0,1,2)` has value `(9 - 2) * 8 = 56`. The other index triplets `(0,1,3)`, `(0,2,3)`, and `(1,2,3)` have values `21`, `3`, and `-18`, respectively. **Example 2** ```text Input: nums = [2,5,9] Output: 0 ``` The only triplet is `(0,1,2)`, with value `(2 - 5) * 9 = -27`. Since every available triplet is negative, return zero. ### Constraints - `3 <= nums.length <= 10^5`. - `1 <= nums[i] <= 10^6`. ### Clarifying Questions - Does the order concern the values or the indices? The indices must satisfy `i < j < k`; the values need not be ordered. - Can a position be used more than once? No; the strict index inequalities require three distinct positions. - What happens if the best value equals zero? Return zero. The negative-only fallback does not change a true maximum of zero. - Is the return value necessarily a 32-bit integer? No; use the provided `long long` return type. ### C++ Interface ```cpp class Solution { public: long long maximumTripletValue(vector<int>& nums) { } }; ``` ### Reasoning Checkpoints - Preserve the order of all three selected indices. - Account for the fallback when no positive value is possible. - Explain the running time at the maximum input length and prevent arithmetic overflow. ```hint Summarize earlier choices When visiting a candidate third index, what information about earlier first and second indices suffices? Update that information only after considering the current position as the third index. ```