Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Fix the middle index j. The best possible positive difference uses the largest value before it, and then the largest value after it maximizes the product because all values are positive. If that best difference is nonpositive, this middle index cannot improve the required nonnegative answer.

Approach

Build prefix maxima and suffix maxima. For every interior index, evaluate (prefixMax[j - 1] - nums[j]) * suffixMax[j + 1] and maximize against an answer initialized to zero. Using positions strictly before and after j enforces distinct ordered indices. Return the maximum without sorting or changing the original order.

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        prefix_max = [0] * n
        suffix_max = [0] * n
        prefix_max[0] = nums[0]
        suffix_max[n - 1] = nums[n - 1]

        for i in range(1, n):
            prefix_max[i] = max(prefix_max[i - 1], nums[i])

        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(nums[i], suffix_max[i + 1])

        res = 0
        for j in range(1, n - 1):
            res = max(res, (prefix_max[j - 1] - nums[j]) * suffix_max[j + 1])
        
        return res

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(n) for prefix-maximum and suffix-maximum arrays.