Maximum Triplet Oscillation — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, find the maximum possible score of an ordered triplet of indices (i, j, k) such that 0 ≤ i < j < k < nums.length, where the score of a triplet is defined by the formula: score(i, j, k) = nums[i] - nums[j] + nums[k].
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Triplet Oscillation"
WHY DOES IT MATTER?
The prefix‑maximum pattern is a cornerstone of interview algorithms because it demonstrates how to convert a combinatorial search into a deterministic scan, reducing exponential blow‑up to linear time. Mastery of this pattern shows you can reason about optimal substructures and avoid unnecessary storage.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that nums[i] - nums[j] + nums[k] can be evaluated incrementally: keep maxLeft = max(nums[i]) and maxDiff = max(maxLeft - nums[j]) as you move forward. This reduces the three‑nested loops to a single pass.
REAL-WORLD CONNECTION
Think of a stock‑trading system that wants to maximize profit from buying, short‑selling, then buying again. The algorithm tracks the best buying price, the best net gain after the short‑sell, and finally the best overall profit, all in real time, mirroring the triplet oscillation computation.
During the interview, write the three‑variable update logic first on paper, then translate it directly into code. Explicitly name the variables (maxPrefix, maxDiff, bestScore) to avoid confusion and to communicate your thought process clearly.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the maximum value of nums[i] - nums[j] + nums[k] under the strict ordering i < j < k. A naïve solution would enumerate every triplet, leading to O(n³) time, which quickly becomes infeasible for n > 10⁴. The key observation is that the expression can be rewritten as (nums[i] - nums[j]) + nums[k]; for each position j we need the best possible nums[i] that appears before it, and for each position k we need the best possible (nums[i] - nums[j]) that appears before k. By scanning the array from left to right while maintaining two running maxima – the maximum value of nums[i] seen so far and the maximum value of (nums[i] - nums[j]) seen so far – we can compute the optimal score for each k in constant time. This transforms the problem into a linear‑time dynamic‑programming style pass, achieving O(n) time and O(1) extra space.
The optimal paradigm falls under the category of "prefix‑maximum" or "running‑best" techniques, which are common when a formula involves a combination of earlier elements and the current element. Instead of storing all previous values, we store only the most promising aggregate (the best prefix value) that can contribute to the final answer. This approach eliminates the combinatorial explosion of the brute‑force method while preserving correctness because the maximum of a set of candidates can be represented by a single scalar value.
Why the naïve approach fails is twofold: time complexity grows cubically, and memory usage can balloon if one attempts to memoize all intermediate results. The linear scan with constant‑space aggregates sidesteps both issues, making the solution scalable to the largest input sizes allowed by typical coding‑interview constraints.
Interview Questions on This Problem
Q1How would you modify the solution if the score formula were nums[i] * nums[j] - nums[k] with i < j < k?
You would need to keep track of the maximum product nums[i] * nums[j] for each j while scanning, which can be done by maintaining the maximum nums[i] seen so far and updating a running maxProduct = max(maxProduct, maxPrefix * nums[j]). Then for each k compute maxProduct - nums[k] and keep the global maximum. This still runs in O(n) time and O(1) space.
Q2Can the algorithm be extended to find the maximum score for a quadruple (i, j, k, l) with score = nums[i] - nums[j] + nums[k] - nums[l]?
Yes. You would maintain three prefix aggregates: maxA = max(nums[i]), maxB = max(nums[i] - nums[j]), and maxC = max(nums[i] - nums[j] + nums[k]) while iterating. When you reach index l you compute candidate = maxC - nums[l] and update the answer. The overall complexity stays O(n) with O(1) extra space.
Q3Why is a single‑pass solution possible here, whereas some similar problems (e.g., maximum sum of three non‑contiguous elements) require O(n²) DP?
Because the expression is linear in each term and the ordering constraint allows us to collapse the dependence into a chain of prefix maxima. In problems where the terms interact multiplicatively or where the ordering is not strict, the optimal substructure may depend on two dimensions, forcing O(n²) DP. Here each new term only needs the best aggregate from the previous prefix, enabling a constant‑time update per element.
Examples
Input
[8, 1, 3, 4, 5]
Output
11
Explanation: Step-by-step: with input [8, 1, 3, 4, 5], we first find all possible triplets (i, j, k) where 0 ≤ i < j < k < nums.length. Then we calculate the score for each triplet using the formula score(i, j, k) = nums[i] - nums[j] + nums[k]. Finally, we return the maximum score found.
Input
[1, 2, 3, 4, 5]
Output
4
Explanation: Step-by-step: with input [1, 2, 3, 4, 5], we first find all possible triplets (i, j, k) where 0 ≤ i < j < k < nums.length. Then we calculate the score for each triplet using the formula score(i, j, k) = nums[i] - nums[j] + nums[k]. Finally, we return the maximum score found.
Constraints
- 3 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Optimal Approach & Strategy
Maintain maxPrefix = max(nums[i]) and maxDiff = max(maxPrefix - nums[j]) while iterating; for each k compute maxDiff + nums[k] and update the answer, achieving O(n) time.
Brute Force Approach
Enumerate every i, j, k triple and compute the score, keeping the maximum; this runs in O(n³) time.
Verified Code Solutions
function solution(nums) {
let maxScore = -Infinity;
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length - 1; j++) {
for (let k = j + 1; k < nums.length; k++) {
let score = nums[i] - nums[j] + nums[k];
maxScore = Math.max(maxScore, score);
}
}
}
return maxScore;
}class Solution {
public:
int solution(vector<int>& nums) {
int maxScore = INT_MIN;
for (int i = 0; i < nums.size() - 2; i++) {
for (int j = i + 1; j < nums.size() - 1; j++) {
for (int k = j + 1; k < nums.size(); k++) {
int score = nums[i] - nums[j] + nums[k];
maxScore = max(maxScore, score);
}
}
}
return maxScore;
}
};class Solution {
public int solution(int[] nums) {
int maxScore = Integer.MIN_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
for (int j = i + 1; j < nums.length - 1; j++) {
for (int k = j + 1; k < nums.length; k++) {
int score = nums[i] - nums[j] + nums[k];
maxScore = Math.max(maxScore, score);
}
}
}
return maxScore;
}
}def solution(nums):
maxScore = float('-inf')
for i in range(len(nums) - 2):
for j in range(i + 1, len(nums) - 1):
for k in range(j + 1, len(nums)):
score = nums[i] - nums[j] + nums[k]
maxScore = max(maxScore, score)
return maxScorefunction solution(nums) {
let maxScore = -Infinity;
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length - 1; j++) {
for (let k = j + 1; k < nums.length; k++) {
let score = nums[i] - nums[j] + nums[k];
maxScore = Math.max(maxScore, score);
}
}
}
return maxScore;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.