3073. Maximum Increasing Triplet Value
Given an array nums, return the maximum 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].
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) {
set<int> st;
vector<int> dp(nums.size(),1e9);
for(int i = 0; i < dp.size(); i++) {
auto it = st.lower_bound(nums[i]);
if(it != begin(st)) {
dp[i] = *prev(it) - nums[i];
}
st.insert(nums[i]);
}
int res = -1e9, best = -1e9;
for(int i = dp.size() - 1; i >= 0; i--) {
if(dp[i] != 1e9 and best > nums[i]) {
res = max(res, best + dp[i]);
}
best = max(best, nums[i]);
}
return res;
}
};
|
