DDSA Solutions

2874. Maximum Value of an Ordered Triplet II

MediumView on LeetCode
Array
Time: O(n)
Space: O(1)

Problem Overview

Maximize value of ordered triple: same as 2873 but different formula.

Intuition

Maximize value of ordered triple: same as 2873 but different formula. nums[i]*nums[j]*nums[k] or (nums[i]-nums[k])*nums[j].

Algorithm

  1. 1Track max so far (for i), max*(max-num) for (i,j pair). Then add nums[k].
  2. 2Single pass: maxVal, maxDiff = max(maxVal - nums[j]), ans = max(maxDiff + nums[k]).

Common Pitfalls

  • •One-pass greedy updating three values: max element, max (A-B), max (A-B)*C.
2874.cs
C#
// 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?

Related Problems