2874. Maximum-Value-Of-An-Ordered-Triplet-II

This is a disaster question to have after yesterdays one since its literally the same question. The only difference is that we need to optimize our solution so that it can handle larger arrays.

Since I’ve already taken a look at the optimal solution to this problem, this question was a freebie.

The basic idea is that we fix the value for k for our triplet. In each iteration, if we fix the value of k, we only need to keep track of the largest possible i and the current largest difference between i and j in the current subarray.

class Solution(object):
    def maximumTripletValue(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        res = 0
        imax = nums[0]
        dmax = nums[0] - nums[1]

        for k in range(2, n):
            res = max(res, dmax * nums[k])
            imax = max(imax, nums[k - 1])
            dmax = max(dmax, imax - nums[k])
        
        return res

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 2m 25s