Skip to content

3073. Maximum Increasing Triplet Value

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int maximumTripletValue(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    vector<int> rightMax(n);  // rightMax[i] := max(nums[i + 1..n))
    set<int> leftSortedSet{nums[0]};

    for (int i = n - 2; i >= 0; --i)
      rightMax[i] = max(nums[i + 1], rightMax[i + 1]);

    for (int j = 1; j < n - 1; ++j) {
      if (const auto it = leftSortedSet.lower_bound(nums[j]);
          it != leftSortedSet.begin() && rightMax[j] > nums[j])
        ans = max(ans, *prev(it) - nums[j] + rightMax[j]);

      leftSortedSet.insert(nums[j]);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int maximumTripletValue(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    int[] rightMax = new int[n]; // rightMax[i] := max(nums[i + 1..n))
    TreeSet<Integer> leftSortedSet = new TreeSet<>(Arrays.asList(nums[0]));

    for (int i = n - 2; i >= 0; --i)
      rightMax[i] = Math.max(nums[i + 1], rightMax[i + 1]);

    for (int j = 1; j < n - 1; ++j) {
      Integer lower = leftSortedSet.lower(nums[j]);
      if (lower != null && rightMax[j] > nums[j])
        ans = Math.max(ans, lower - nums[j] + rightMax[j]);
      leftSortedSet.add(nums[j]);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
from sortedcontainers import SortedSet


class Solution:
  def maximumTripletValue(self, nums: list[int]) -> int:
    ans = 0
    rightMax = [0] * len(nums)  # rightMax[i] := max(nums[i + 1..n))
    leftSortedSet = SortedSet([nums[0]])

    for i in range(len(nums) - 2, -1, -1):
      rightMax[i] = max(nums[i + 1], rightMax[i + 1])

    for j in range(1, len(nums) - 1):
      i = bisect.bisect_left(leftSortedSet, nums[j])
      if i > 0 and rightMax[j] > nums[j]:
        ans = max(ans, leftSortedSet[i - 1] - nums[j] + rightMax[j])
      leftSortedSet.add(nums[j])

    return ans