LeetCode Entry

2874. Maximum Value of an Ordered Triplet II

03.04.2025 medium 2025 kotlin rust

Max (a[i] - a[j]) a[k]

2874. Maximum Value of an Ordered Triplet II medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/947

Problem TLDR

Max (a[i] - a[j]) * a[k] #medium

Intuition

Same as previous (https://t.me/leetcode_daily_unstoppable/946), but more time contrained.

Compute max so-far, then max diff so-far, then max of max diff * a[i].

Approach

  • I’ve already golfed it yesterday
  • but how about to use just a single extra variable?
  • how about no extra variables?

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    var d = 0
    fun maximumTripletValue(a: IntArray) = a.maxOf { x ->
    1L * d * x.also { a[0] = max(a[0], x); d = max(d, a[0] - x) }}



    fun maximumTripletValue(a: IntArray) = (2..<a.size).maxOf { i ->
    if (i < 3) { a[1] = a[0] - a[1].also { a[0] = max(a[0], a[1]) }}
    1L * max(0, a[1]) * a[i].also {
        if (a[i] > a[0]) a[0] = a[i]; a[1] = max(a[1], a[0] - a[i]) }}



    pub fn maximum_triplet_value(a: Vec<i32>) -> i64 {
        a.iter().fold((0, 0, 0), |(r, d, m), &x|
        (r.max(d as i64 * x as i64), d.max(x.max(m) - x), x.max(m))).0
    }



    long long maximumTripletValue(vector<int>& a) {
        long long r = 0, m = 0, d = 0;
        for (int x: a) r = max(r, d * x), m = max(m, 1LL * x), d = max(d, m - x);
        return r;
    }