Find the maximum value of an ordered triplet expression over an integer array.
Given an integer array nums, choose indices i < j < k and maximize the value of an ordered triplet expression of the form (nums[i] - nums[j]) * nums[k].
Your task is to return the largest possible value among all valid triplets. If every valid triplet produces a negative value, return that maximum negative value.
This is a classic array-optimization problem where the key is to evaluate the best prefix contribution before each middle index and the best suffix contribution after it.
Input Format
- An integer array
nums. - The array length is at least 3.
- Each element is an integer.
Output Format
- Return a single integer: the maximum value of
(nums[i] - nums[j]) * nums[k]over alli < j < k.
Constraints
3 <= nums.length- Values are integers.
- The answer may be negative if no positive triplet exists.
Example 1
Input
nums = [12, 6, 1, 2, 7]
Output
77
Explanation
Choose i = 0, j = 2, k = 4. Then (12 - 1) * 7 = 77, which is the maximum possible value.
Example 2
Input
nums = [1, 10, 3, 4, 19]
Output
133
Explanation
Choose i = 1, j = 2, k = 4. Then (10 - 3) * 19 = 133.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.