Maximum Increasing Triplet Value

Problem

Given an array nums, return themaximum value of a triplet (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k].

The value of a triplet (i, j, k) is nums[i] - nums[j] + nums[k].

Examples

Example 1:

Input: nums = [5,6,9]
Output: 8
Explanation: We only have one choice for an increasing triplet and that is
choosing all three elements. The value of this triplet would be `5 - 6 + 9 =
8`.

Example 2:

Input: nums = [1,5,3,6]
Output: 4
Explanation: There are only two increasing triplets:
`(0, 1, 3)`: The value of this triplet is `nums[0] - nums[1] + nums[3] = 1 - 5
+ 6 = 2`.
`(0, 2, 3)`: The value of this triplet is `nums[0] - nums[2] + nums[3] = 1 - 3
+ 6 = 4`.
Thus the answer would be `4`.

Constraints:

• 3 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• The input is generated such that at least one triplet meets the given condition.

Solution

Method 1 – Prefix Min and Suffix Max

Intuition

To maximize the value of a triplet (i, j, k) with i < j < k and nums[i] < nums[j] < nums[k], we want to maximize nums[i] - nums[j] + nums[k]. For each j, we can keep track of the minimum nums[i] to the left and the maximum nums[k] to the right, and check if a valid triplet exists.

Approach

1. For each index, compute the minimum value to its left (prefix min).
2. For each index, compute the maximum value to its right (suffix max).
3. For each index j from 1 to n-2:
   • If prefix_min[j-1] < nums[j] < suffix_max[j+1], compute the value: prefix_min[j-1] - nums[j] + suffix_max[j+1].
   • Track the maximum value found.
4. Return the maximum value, or 0 if no valid triplet exists.

Code

C++

class Solution {
public:
    int maximumTripletValue(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        vector<int> pre_min(n), suf_max(n);
        pre_min[0] = nums[0];
        for (int i = 1; i < n; ++i) pre_min[i] = min(pre_min[i-1], nums[i]);
        suf_max[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i) suf_max[i] = max(suf_max[i+1], nums[i]);
        for (int j = 1; j < n-1; ++j) {
            if (pre_min[j-1] < nums[j] && nums[j] < suf_max[j+1]) {
                ans = max(ans, pre_min[j-1] - nums[j] + suf_max[j+1]);
            }
        }
        return ans;
    }
};

Go

func maximumTripletValue(nums []int) int {
    n := len(nums)
    preMin := make([]int, n)
    sufMax := make([]int, n)
    preMin[0] = nums[0]
    for i := 1; i < n; i++ {
        if nums[i] < preMin[i-1] {
            preMin[i] = nums[i]
        } else {
            preMin[i] = preMin[i-1]
        }
    }
    sufMax[n-1] = nums[n-1]
    for i := n-2; i >= 0; i-- {
        if nums[i] > sufMax[i+1] {
            sufMax[i] = nums[i]
        } else {
            sufMax[i] = sufMax[i+1]
        }
    }
    ans := 0
    for j := 1; j < n-1; j++ {
        if preMin[j-1] < nums[j] && nums[j] < sufMax[j+1] {
            v := preMin[j-1] - nums[j] + sufMax[j+1]
            if v > ans {
                ans = v
            }
        }
    }
    return ans
}

Java

class Solution {
    public int maximumTripletValue(int[] nums) {
        int n = nums.length, ans = 0;
        int[] preMin = new int[n], sufMax = new int[n];
        preMin[0] = nums[0];
        for (int i = 1; i < n; ++i) preMin[i] = Math.min(preMin[i-1], nums[i]);
        sufMax[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i) sufMax[i] = Math.max(sufMax[i+1], nums[i]);
        for (int j = 1; j < n-1; ++j) {
            if (preMin[j-1] < nums[j] && nums[j] < sufMax[j+1]) {
                ans = Math.max(ans, preMin[j-1] - nums[j] + sufMax[j+1]);
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maximumTripletValue(nums: IntArray): Int {
        val n = nums.size
        val preMin = IntArray(n)
        val sufMax = IntArray(n)
        preMin[0] = nums[0]
        for (i in 1 until n) preMin[i] = minOf(preMin[i-1], nums[i])
        sufMax[n-1] = nums[n-1]
        for (i in n-2 downTo 0) sufMax[i] = maxOf(sufMax[i+1], nums[i])
        var ans = 0
        for (j in 1 until n-1) {
            if (preMin[j-1] < nums[j] && nums[j] < sufMax[j+1]) {
                ans = maxOf(ans, preMin[j-1] - nums[j] + sufMax[j+1])
            }
        }
        return ans
    }
}

Python

class Solution:
    def maximumTripletValue(self, nums: list[int]) -> int:
        n = len(nums)
        pre_min = [0] * n
        suf_max = [0] * n
        pre_min[0] = nums[0]
        for i in range(1, n):
            pre_min[i] = min(pre_min[i-1], nums[i])
        suf_max[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            suf_max[i] = max(suf_max[i+1], nums[i])
        ans = 0
        for j in range(1, n-1):
            if pre_min[j-1] < nums[j] < suf_max[j+1]:
                ans = max(ans, pre_min[j-1] - nums[j] + suf_max[j+1])
        return ans

Rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut pre_min = vec![0; n];
        let mut suf_max = vec![0; n];
        pre_min[0] = nums[0];
        for i in 1..n {
            pre_min[i] = pre_min[i-1].min(nums[i]);
        }
        suf_max[n-1] = nums[n-1];
        for i in (0..n-1).rev() {
            suf_max[i] = suf_max[i+1].max(nums[i]);
        }
        let mut ans = 0;
        for j in 1..n-1 {
            if pre_min[j-1] < nums[j] && nums[j] < suf_max[j+1] {
                ans = ans.max(pre_min[j-1] - nums[j] + suf_max[j+1]);
            }
        }
        ans
    }
}

TypeScript

class Solution {
    maximumTripletValue(nums: number[]): number {
        const n = nums.length;
        const preMin = Array(n).fill(0), sufMax = Array(n).fill(0);
        preMin[0] = nums[0];
        for (let i = 1; i < n; ++i) preMin[i] = Math.min(preMin[i-1], nums[i]);
        sufMax[n-1] = nums[n-1];
        for (let i = n-2; i >= 0; --i) sufMax[i] = Math.max(sufMax[i+1], nums[i]);
        let ans = 0;
        for (let j = 1; j < n-1; ++j) {
            if (preMin[j-1] < nums[j] && nums[j] < sufMax[j+1]) {
                ans = Math.max(ans, preMin[j-1] - nums[j] + sufMax[j+1]);
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), since we make three passes through the array.
• 🧺 Space complexity: O(n), for the prefix min and suffix max arrays.