Problem Statement in English

You are given an integer array.

Your task is to maximise the value of (nums[i] - nums[j]) * nums[k] where i < j < k.

Approach

The trick here is to keep track of $i$ while iterating over $k$.

It’s probably best to read the code for this one.

Solution in Python


class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        i = nums[0]
        max_diff = res = 0

        for k in nums[1:]:
            res = max(res, max_diff*k)

            i = max(i, k)
            max_diff = max(max_diff, i-k)

        return res

Complexity

  • Time: $O(n)$
    Since we iterate over the array once, the time complexity is linear.

  • Space: $O(1)$
    Since we are only using a few variables to keep track of the maximum difference and the result, the space complexity is constant.

Mistakes I Made

I had to look this one up :(

And we are done.