Find Max Triplet With A Condition

Given an array of integers, find three numbers in the array such that (a[i]-a[j]) *a[k] is maximium and i < j < k. This is a problem from leetcode at this link .

Solution: Solution

In the following solution, we find the max value on left and right side of each position in the array. To maximize the outcome, the first and third term needs to be maximum. Thus we find the max on each side, and compute the result to search for max meeting the condition specified.

class Solution: def maximumTripletValue(self, nums: List[int]) -> int: n = len(nums) # let us create max array that hold max items that lie towards the left of a position lmax = [float('inf')]*n lmax[0] = nums[0] for i in range(1,n): lmax[i] = max(lmax[i-1],nums[i-1]) print(f"lmax is {lmax}") # similarly for right side rmax = [float('inf')]*n rmax[n-1] = nums[n-1] for i in range(n-2,-1,-1): rmax[i] = max(rmax[i+1],nums[i+1]) print(f"rmax is {rmax}") ret_val = -9999999 for idx in range(1,n-1): triplet = (lmax[idx]-nums[idx])*rmax[idx] if triplet > ret_val: ret_val = triplet if ret_val <0: return 0 else: return ret_val