Skip to content

2874. Maximum Value of an Ordered Triplet II 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  // Same as 2873. Maximum Value of an Ordered Triplet I
  long long maximumTripletValue(vector<int>& nums) {
    long long ans = 0;
    int maxDiff = 0;  // max(nums[i] - nums[j])
    int maxNum = 0;   // max(nums[i])

    for (const int num : nums) {
      ans = max(ans, static_cast<long long>(maxDiff) * num);  // num := nums[k]
      maxDiff = max(maxDiff, maxNum - num);                   // num := nums[j]
      maxNum = max(maxNum, num);                              // num := nums[i]
    }

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  // Same as 2873. Maximum Value of an Ordered Triplet I
  public long maximumTripletValue(int[] nums) {
    long ans = 0;
    int maxDiff = 0; // max(nums[i] - nums[j])
    int maxNum = 0;  // max(nums[i])

    for (final int num : 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;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  # Same as 2873. Maximum Value of an Ordered Triplet I
  def maximumTripletValue(self, nums: List[int]) -> int:
    ans = 0
    maxDiff = 0  # max(nums[i] - nums[j])
    maxNum = 0   # max(nums[i])

    for num in nums:
      ans = max(ans, maxDiff * num)         # num := nums[k]
      maxDiff = max(maxDiff, maxNum - num)  # num := nums[j]
      maxNum = max(maxNum, num)             # num := nums[i]

    return ans