2873. Maximum Value of an Ordered Triplet I

Time: O(n)

Space: O(1)

Intuition

Maximum value of ordered triple (i<j<k): nums[i]-nums[j]+nums[k]. Fix j as middle, maximize nums[i] to the left and nums[k] to the right.

Algorithm

1For each j: prefix_max[j] = max of nums[0..j-1]. suffix_max[j] = max of nums[j+1..n-1].
2ans = max over j of (prefix_max[j] - nums[j] + suffix_max[j]).

Common Pitfalls

•Negative contribution at j is fine. Precompute prefix max and suffix max in O(n).

2873.cs

// Approach: Track max prefix, max (prefix - mid); answer = max(prefix - mid) * suffix.
// Time: O(n) Space: O(1)

public class Solution
{
    public long MaximumTripletValue(int[] nums)
    {
        long ans = 0;
        int maxDiff = 0; // max(nums[i] - nums[j])
        int maxNum = 0;  // max(nums[i])

        foreach (var num in nums)
        {
            ans = Math.Max(ans, (long)maxDiff * num); // num := nums[k]
            maxDiff = Math.Max(maxDiff, maxNum - num); // num := nums[j]
            maxNum = Math.Max(maxNum, num);            // num := nums[i]
        }

        return ans;
    }
}

Was this solution helpful?