Problem Statement in English

You’re given a 0-indexed integer array nums of length n and an integer k.

You need to find the maximum value of the expression nums[i] - nums[j] * nums[k] where i < j < k.

Basically, the position of the $i$th element is the first element, the $j$th element is the second element, and the $k$th element is the third element.

You’re allowed to pick any $j$ and $k$, such that $j$ is less than $k$, and $i$ is less than $j$.

Approach

It’s quite straightforward to come up with an $O(n^3)$ solution, and in fact, in this case that will pass, considering that the maximum length of nums is $10^3$.

But we can do better. We can do this in $O(n^2)$ time.

We can do this by using a single loop to iterate through the array and keep track of the maximum value of nums[i] - nums[j] for all j less than the current index.

This will need a nested loop.

Afterwards, we can use one pass of the array to simply multiply the maximum value of nums[i] - nums[j] with the current value of nums[k].

The only extra piece is that the best difference that we find is also valid for all future j values.

Solution in Python


class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        l = len(nums)

        best_diff = [0] * l

        for j in range(1, l - 1):
            for i in range(j):
                best_diff[j + 1] = max(best_diff[j + 1], nums[i] - nums[j])
            best_diff[j + 1] = max(best_diff[j + 1], best_diff[j])

        res = 0
        for k in range(2, l):
            res = max(res, best_diff[k] * nums[k])

        return res

Complexity

  • Time: $O(n^2)$
    Since we use a nested loop for finding the best difference, and then a single loop to find the maximum value of nums[i] - nums[j] * nums[k].

  • Space: $O(n)$
    Since we use an array of size $n$ to store the best difference.

Mistakes I Made

I didn’t realize that the best difference is valid for all future j values, and hadn’t added that one extra line.

And we are done.