Maximum Value of an Ordered Triplet I - Practice Coding Problems

Maximum Value of an Ordered Triplet I - Problem

Array Easy

You are given a 0-indexed integer array nums.

Return the maximum value over all triplets of indices (i, j, k) such that i < j < k. If all such triplets have a negative value, return 0.

The value of a triplet of indices (i, j, k) is equal to (nums[i] - nums[j]) * nums[k].

Input & Output

Example 1 — Basic Case

$ Input: nums = [12,6,1,2,7]

› Output: 77

💡 Note: The maximum value is achieved at triplet (0,2,4): (12-1)*7 = 11*7 = 77

Example 2 — All Negative

$ Input: nums = [1,10,3,4,19]

› Output: 133

💡 Note: Maximum triplet is (0,2,4): (1-3)*19 = -2*19 = -38, but (1,2,4): (10-3)*19 = 7*19 = 133

Example 3 — Small Array

$ Input: nums = [1,2,3]

› Output: 0

💡 Note: Only one triplet (0,1,2): (1-2)*3 = -1*3 = -3, which is negative, so return 0

Constraints

3 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array: [12, 6, 1, 2, 7]

Process

Find triplet (i,j,k) that maximizes (nums[i] - nums[j]) * nums[k]

Output

Maximum value: 77 from triplet (0,2,4)

Key Takeaway

🎯 Key Insight: For each k, efficiently track the maximum difference (nums[i] - nums[j]) seen so far

Asked in

a Amazon 15 M Microsoft 12

The key insight is to recognize that for each position k, we need to find the maximum value of (nums[i] - nums[j]) where i < j < k. The optimal approach uses O(n²) time by tracking the maximum difference efficiently rather than checking all O(n³) triplets. Best approach: Optimized tracking. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Track Maximum Difference	O(n²)	O(1)	For each k, track the maximum (nums[i] - nums[j]) where i < j < k
Brute Force - Check All Triplets	O(n³)	O(1)	Try all possible triplets (i,j,k) where i < j < k

Optimized - Track Maximum Difference — Algorithm Steps

For each position k from 2 to n-1, track max difference seen so far
For each position j from 1 to k-1, update max difference with (max_so_far - nums[j])
Calculate current triplet value as max_difference * nums[k]
Update global maximum and track maximum element seen

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Max

For each k, maintain max(nums[i] - nums[j]) where i < j < k

Calculate

Multiply max difference by nums[k]

Update

Keep track of global maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long max_ll(long long a, long long b) {
    return a > b ? a : b;
}

int max_int(int a, int b) {
    return a > b ? a : b;
}

long long solution(int* nums, int n) {
    if (n < 3) return 0;
    
    long long maxValue = 0;
    
    for (int k = 2; k < n; k++) {
        long long maxDiff = LLONG_MIN;
        int maxI = nums[0];
        
        for (int j = 1; j < k; j++) {
            maxDiff = max_ll(maxDiff, (long long)maxI - nums[j]);
            maxI = max_int(maxI, nums[j]);
        }
        
        if (maxDiff != LLONG_MIN) {
            long long currentValue = maxDiff * nums[k];
            maxValue = max_ll(maxValue, currentValue);
        }
    }
    
    return maxValue;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long result = solution(nums, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Double nested loop: outer loop for k, inner loop for j

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum values

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Track Maximum Difference — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler