2874.maximum-value-of-an-ordered-triplet-ii.md

2874. Maximum Value of an Ordered Triplet II

Enumeration

To find the maximum value of (nums[i] - nums[j]) * nums[k] where i < j < k, we want to maximum nums[i] and nums[k], and minimum nums[j]. So we pre-compute the maximum of nums[i] from left and nums[k] from right. Then we iterate nums[j] as minimum to find the global maximum value.

def maximumTripletValue(self, nums: List[int]) -> int:
    # (A[i] - A[j]) * A[k]
    #  max    min     max
    # (    max    ) * max
    n = len(nums)
    left_max = [0] * n
    right_max = [0] * n
    left_max[0] = nums[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], nums[i])
    right_max[-1] = nums[-1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], nums[i])
    
    answer = -inf
    for i in range(1, n - 1):
        answer = max(answer, (left_max[i - 1] - nums[i]) * right_max[i + 1])
    return answer if answer > 0 else 0

fun maximumTripletValue(nums: IntArray): Long {
    val n = nums.size
    val leftMax = IntArray(n) { Int.MIN_VALUE }
    val rightMax = IntArray(n) { Int.MIN_VALUE }
    leftMax[0] = nums[0]
    for (i in 1 until n) {
        leftMax[i] = maxOf(leftMax[i - 1], nums[i])
    }
    rightMax[n - 1] = nums[n - 1]
    for (i in n - 2 downTo 0) {
        rightMax[i] = maxOf(rightMax[i + 1], nums[i])
    }
    var result = Long.MIN_VALUE
    for (i in 1 until n - 1) {
        result = maxOf(result, (leftMax[i - 1] - nums[i]).toLong() * rightMax[i + 1])
    }
    return if (result < 0) 0 else result
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Space Optimized

We can optimize the space complexity to O(1) by keeping track of the maximum of (nums[i] - nums[j]) when iterating k.

1. To maximize (nums[i] - nums[j]) * nums[k] when iterate k, we need to keep track for the maximum of (nums[i] - nums[j]).
2. To maximize (nums[i] - nums[j]), we need to keep track of the maximum of nums[i] when iterating nums[j].

During the iteration of k, we keep track of:

• nums[k] as the 3rd number.
• Maximum of (nums[i] - nums[j]) we have seen so far before k.
• Maximum of 1st number nums[i] we have seen so far before j.

We don't store the first maximum and second minimum then iterating the third maximum, because the second minimum might be before the first maximum, that violate the order of i < j < k.

nums = [1, 10, 5, ...]
        j   i  k
        * secondMin
            * firstMax

def maximumTripletValue(self, nums: List[int]) -> int:
    if len(nums) < 3: return 0
    i_max = 0
    max_diff = 0
    result = 0
    for i in range(len(nums)):
        result = max(result, max_diff * nums[i])
        max_diff = max(max_diff, i_max - nums[i])
        i_max = max(i_max, nums[i])
    return result

fun maximumTripletValue(nums: IntArray): Long {
    if (nums.size < 3) return 0L
    var iMax = 0        // The maximum of nums[i] we have seen so far
    var maxDiff = 0     // The maximum of (nums[i] - nums[j]) we have seen so far
    var result = 0L
    // Iterate nums[k] as the 3rd number
    for (k in 0 until nums.size) {
        result = maxOf(result, maxDiff * nums[k].toLong())
        // The order to update `maxDiff` and `iMax` matters, if we update `iMax` first `maxDiff` later, we use `nums[k]` as the 1st number, which leads to wrong result because `nums[i]` might be after `nums[j]`.
        // We use `nums[k]` as the 2nd number, we update (nums[i] - nums[j]) for the next iteration
        maxDiff = maxOf(maxDiff, iMax - nums[k])
        // We use `nums[k]` as the 1st number, we update the maximum of nums[i] for the next iteration
        iMax = maxOf(iMax, nums[k])
    }
    return result
}

• Time Complexity: O(n).
• Space Complexity: O(1).