LeetCode Entry

2016. Maximum Difference Between Increasing Elements

16.06.2025 easy 2025 kotlin rust

Max increasing pair diff

2016. Maximum Difference Between Increasing Elements easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1021

Problem TLDR

Max increasing pair diff #easy

Intuition

Brute-force works. Or, compute running min and search max(current - min).

Approach

• shortest code can be the optimal too

Complexity

• Time complexity: \(O(n^2)\), or O(n)

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

Code

// 78ms
    fun maximumDifference(n: IntArray) =
        (0..<n.lastIndex).maxOf { i -> n.drop(i + 1).maxOf { it - n[i] }}
        .takeIf { it > 0 } ?: -1

// 37ms
    fun maximumDifference(n: IntArray) =
        (0..<n.lastIndex).maxOf { i ->
        (i + 1..<n.size).maxOf { j -> n[j] - n[i] }}
        .takeIf { it > 0 } ?: -1

// 3ms
    fun maximumDifference(n: IntArray) =
        n.fold(n[0] to 0) { (m, r), t -> min(t, m) to max(r, t - m) }
        .second.takeIf { it > 0 } ?: -1

// 1ms
    fun maximumDifference(n: IntArray): Int {
        var min = n[0]; var r = 0
        for (x in n) {
            r = max(r, x - min)
            min = min(min, x)
        }
        return if (r > 0) r else -1
    }

// 0ms
    pub fn maximum_difference(n: Vec<i32>) -> i32 {
        let x = n.iter().fold((0, n[0]), |(r, m), &x| (r.max(x - m), m.min(x))).0;
        if x > 0 { x } else { -1 }
    }

// 0ms
    int maximumDifference(vector<int>& n) {
        int r = 0, m = n[0];
        for (int x: n) r = max(r, x - m), m = min(m, x);
        return r > 0 ? r : -1;
    }