mediumArraysPattern: Basic Traversal
Maximum Triplet Oscillation Solution
Problem Statement
Given an integer array `nums`, find the maximum possible score of an ordered triplet of indices $(i, j, k)$ such that $0 \le i < j < k < \text{nums.length}$. The score of a triplet is defined by the formula: $$\text{score}(i, j, k) = nums[i] - nums[j] + nums[k]$$ Return the maximum score among all valid triplets.
Examples
Example 1:
Input:nums = [4, 2, 8, 1, 5]
Output:12
Explanation: The optimal triplet is at indices (2, 3, 4) corresponding to values (8, 1, 5). The score is 8 - 1 + 5 = 12.
Example 2:
Input:nums = [1, 5, 2, 6]
Output:9
Explanation: The optimal triplet is at indices (1, 2, 3) corresponding to values (5, 2, 6). The score is 5 - 2 + 6 = 9.
Example 3:
Input:nums = [10, 10, 10]
Output:10
Explanation: There is only one valid triplet at indices (0, 1, 2) with values (10, 10, 10). The score is 10 - 10 + 10 = 10.
Constraints
- 3 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Time: O(N) Space: O(1)
We can optimize this to O(N) time by maintaining three running variables in a single pass: max_i (the maximum value seen so far to act as i), max_diff (the maximum value of nums[i] - nums[j] seen so far), and max_score (the maximum score nums[i] - nums[j] + nums[k]). For each element, we update max_score using the current max_diff, update max_diff using the current max_i, and finally update max_i with the current element.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
class Solution:
def max_triplet_oscillation(self, nums: list[int]) -> int:
n = len(nums)
if n < 3:
return 0
max_i = nums[0]
max_diff = float('-inf')
max_score = float('-inf')
for j in range(1, n - 1):
max_i = max(max_i, nums[j - 1])
max_diff = max(max_diff, max_i - nums[j])
max_score = max(max_score, max_diff + nums[j + 1])
return int(max_score)