# Maximum Value of an Ordered Triplet I
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-value-of-an-ordered-triplet-i)
Canonical: https://scaleengineer.com/dsa/problems/maximum-value-of-an-ordered-triplet-i
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
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]`.

**Example 1:**

**Input:** nums = [12,6,1,2,7]
**Output:** 77
**Explanation:** The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77.
It can be shown that there are no ordered triplets of indices with a value greater than 77. 

**Example 2:**

**Input:** nums = [1,10,3,4,19]
**Output:** 133
**Explanation:** The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133.
It can be shown that there are no ordered triplets of indices with a value greater than 133.

**Example 3:**

**Input:** nums = [1,2,3]
**Output:** 0
**Explanation:** The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.

**Constraints:**

* `3 <= nums.length <= 100`
* `1 <= nums[i] <= 106`

# Approaches
## Brute Force with Triple Loop
The most straightforward solution is to exhaustively check every possible ordered triplet `(i, j, k)` where `i < j < k`. We can use three nested loops to iterate through all combinations of indices, calculate the value `(nums[i] - nums[j]) * nums[k]` for each, and keep track of the maximum value found. Since the problem asks for 0 if the maximum value is negative, initializing our result to 0 handles this case.
**Time:** O(n³), where n is the length of `nums`. We have three nested loops, each potentially iterating up to `n` times, leading to a cubic relationship with the input size. · **Space:** O(1), as we only use a few variables to store the indices and the maximum value, regardless of the input size.
**Pros:** Simple to understand and implement.; Correctly solves the problem by exploring the entire search space.
**Cons:** Highly inefficient due to its cubic time complexity.; Will be too slow for larger input sizes (though it passes for the given constraints).
### Explanation
This approach directly translates the problem statement into code. We set up three nested loops to generate all valid index triplets `(i, j, k)`.

- The outer loop iterates `i` from `0` to `n-3`.
- The middle loop iterates `j` from `i+1` to `n-2`.
- The inner loop iterates `k` from `j+1` to `n-1`.

Inside the innermost loop, we have a valid triplet. We calculate its value, ensuring we use a `long` type to prevent potential integer overflow. We then compare this value with our running maximum and update it if the new value is greater. This process guarantees that we check every single possibility and find the global maximum.

```java
class Solution {
    public long maximumValue(int[] nums) {
        long maxVal = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    long currentVal = (long)(nums[i] - nums[j]) * nums[k];
                    if (currentVal > maxVal) {
                        maxVal = currentVal;
                    }
                }
            }
        }
        return maxVal;
    }
}
```
### Algorithm
- Initialize a variable `maxVal` to 0.
- Use three nested loops to iterate through all possible ordered triplets of indices `(i, j, k)` such that `i < j < k`.
- For each triplet, calculate the value `currentVal = (long)(nums[i] - nums[j]) * nums[k]`.
- Update `maxVal` by taking the maximum of `maxVal` and `currentVal`.
- After checking all triplets, return `maxVal`.

## Optimized Iteration by Fixing the Middle Index
We can improve upon the brute-force approach by making a key observation. For a fixed middle index `j`, to maximize the expression `(nums[i] - nums[j]) * nums[k]`, we need to maximize the term `(nums[i] - nums[j])` and the term `nums[k]` independently. Since `nums[k]` is always positive, this means we should find the largest possible `nums[i]` for `i < j` and the largest possible `nums[k]` for `k > j`. This insight allows us to reduce the number of loops from three to two.
**Time:** O(n²). The main loop for `j` runs `n-2` times. Inside this loop, finding `max_i_val` takes O(j) time and finding `max_k_val` takes O(n-j) time. The total work for each `j` is O(n), leading to an overall complexity of O(n²). · **Space:** O(1), as we only use a constant number of variables.
**Pros:** More efficient than the triple loop brute-force approach.; The logic is a direct optimization based on the structure of the expression.
**Cons:** Still inefficient for large inputs.; Involves redundant calculations, as the prefix and suffix maximums are re-calculated from scratch for each `j`.
### Explanation
Instead of three nested loops, we can iterate with a single main loop for the middle index `j`. For each `j`, we then perform two separate searches:
1.  A search for the maximum value in the subarray to the left of `j` (`nums[0...j-1]`).
2.  A search for the maximum value in the subarray to the right of `j` (`nums[j+1...n-1]`).

Once we have these two maximums (`max_i_val` and `max_k_val`), we can calculate the best possible triplet value for that specific `j`. We update our global maximum with this value and continue the process for all possible `j`'s.

```java
class Solution {
    public long maximumValue(int[] nums) {
        long maxVal = 0;
        int n = nums.length;
        for (int j = 1; j < n - 1; j++) {
            int max_i = 0;
            for (int i = 0; i < j; i++) {
                if (nums[i] > max_i) {
                    max_i = nums[i];
                }
            }
            
            if (max_i > nums[j]) {
                int max_k = 0;
                for (int k = j + 1; k < n; k++) {
                    if (nums[k] > max_k) {
                        max_k = nums[k];
                    }
                }
                long currentVal = (long)(max_i - nums[j]) * max_k;
                if (currentVal > maxVal) {
                    maxVal = currentVal;
                }
            }
        }
        return maxVal;
    }
}
```
### Algorithm
- Initialize `maxVal = 0`.
- Iterate through each possible middle index `j` from `1` to `n-2`.
- For each `j`, find the maximum element in the prefix `nums[0...j-1]`, let's call it `max_i_val`.
- For the same `j`, find the maximum element in the suffix `nums[j+1...n-1]`, let's call it `max_k_val`.
- If `max_i_val > nums[j]`, calculate the potential maximum value as `currentVal = (long)(max_i_val - nums[j]) * max_k_val`.
- Update `maxVal = max(maxVal, currentVal)`.
- Return `maxVal`.

## Linear Scan with Precomputation
The O(n²) approach can be further optimized by eliminating the repeated computations of prefix and suffix maximums. We can precompute these values once and store them in auxiliary arrays. This allows us to find the required maximums for any middle index `j` in constant time, leading to a linear time solution.
**Time:** O(n). We have three separate loops, each running `n` times (one for prefix max, one for suffix max, one for the final calculation). The total time is O(n) + O(n) + O(n) = O(n). · **Space:** O(n) for the `prefixMax` and `suffixMax` arrays.
**Pros:** Achieves an efficient linear time complexity.; The logic is a clear trade-off between space and time.
**Cons:** Requires extra space proportional to the input size.
### Explanation
This approach consists of three main steps:
1.  **Prefix Maximums:** Create an array `prefixMax` of the same size as `nums`. Traverse `nums` from left to right, filling `prefixMax` such that `prefixMax[i]` holds the maximum value found in `nums` from index `0` up to `i`.
2.  **Suffix Maximums:** Create another array `suffixMax`. Traverse `nums` from right to left, filling `suffixMax` such that `suffixMax[i]` holds the maximum value from index `i` to the end of the array.
3.  **Final Calculation:** Iterate through the middle index `j` from `1` to `n-2`. For each `j`, the maximum `nums[i]` (with `i < j`) is `prefixMax[j-1]` and the maximum `nums[k]` (with `k > j`) is `suffixMax[j+1]`. We can now calculate the triplet value in O(1) and update the overall maximum.

```java
class Solution {
    public long maximumValue(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;

        int[] prefixMax = new int[n];
        prefixMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
        }

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

        long maxVal = 0;
        for (int j = 1; j < n - 1; j++) {
            long val_i = prefixMax[j - 1];
            long val_j = nums[j];
            long val_k = suffixMax[j + 1];
            
            if (val_i > val_j) {
                long currentVal = (val_i - val_j) * val_k;
                if (currentVal > maxVal) {
                    maxVal = currentVal;
                }
            }
        }
        return maxVal;
    }
}
```
### Algorithm
- Create a `prefixMax` array where `prefixMax[i]` stores `max(nums[0...i])`.
- Create a `suffixMax` array where `suffixMax[i]` stores `max(nums[i...n-1])`.
- Initialize `maxVal = 0`.
- Iterate `j` from `1` to `n-2`.
- For each `j`, the maximum `nums[i]` for `i < j` is `prefixMax[j-1]`.
- The maximum `nums[k]` for `k > j` is `suffixMax[j+1]`.
- Calculate `currentVal = (long)(prefixMax[j-1] - nums[j]) * suffixMax[j+1]`.
- Update `maxVal = max(maxVal, currentVal)`.
- Return `maxVal`.

## Optimal Single Pass Linear Scan
The most optimal solution achieves both linear time and constant space complexity by processing the array in a single pass. This dynamic programming-style approach cleverly maintains the maximums needed at each step. As we iterate through the array, we consider each element as a potential `nums[k]`, `nums[j]`, and `nums[i]` in a specific order to build up the solution.
**Time:** O(n), as we iterate through the array only once. · **Space:** O(1), as we only use a few variables to store the running maximums.
**Pros:** Most efficient solution with O(n) time and O(1) space.; Processes the array in a single pass.
**Cons:** The logic can be less intuitive to grasp compared to more direct approaches.
### Explanation
We iterate through the array while maintaining two key values:
- `max_i`: The maximum value of an element seen so far (a potential `nums[i]`).
- `max_ij`: The maximum difference `nums[i] - nums[j]` seen so far.

For each number `num` in the array, we perform three updates in a specific order:
1.  **Treat `num` as `nums[k]`**: We calculate a potential answer by multiplying `num` with the best `(nums[i] - nums[j])` difference (`max_ij`) found among the elements *before* `num`. We update our overall `maxVal` with this result.
2.  **Treat `num` as `nums[j]`**: We update `max_ij`. A new, larger difference might be formed by using `num` as `nums[j]` and the largest element seen before it (`max_i`) as `nums[i]`. So we update `max_ij = max(max_ij, max_i - num)`.
3.  **Treat `num` as `nums[i]`**: We update `max_i` by comparing it with the current `num`. This ensures `max_i` is ready for future elements to use as their potential `nums[j]` or `nums[k]`.

The strict order of these updates is crucial for the correctness of the algorithm.

```java
class Solution {
    public long maximumValue(int[] nums) {
        long maxVal = 0;
        int max_i = 0;
        int max_ij = 0;

        for (int num : nums) {
            // Current num is nums[k]. max_ij is max(nums[i] - nums[j]) for i < j < k.
            maxVal = Math.max(maxVal, (long)max_ij * num);

            // Current num is nums[j]. max_i is max(nums[i]) for i < j.
            max_ij = Math.max(max_ij, max_i - num);

            // Current num is nums[i]. Update max_i for future iterations.
            max_i = Math.max(max_i, num);
        }
        return maxVal;
    }
}
```
### Algorithm
- Initialize `maxVal = 0`, `max_i = 0`, and `max_ij = 0`.
- `max_i` will track the maximum `nums[i]` seen so far.
- `max_ij` will track the maximum `nums[i] - nums[j]` seen so far.
- Iterate through each `num` in the `nums` array.
- In each iteration, first update the result: `maxVal = max(maxVal, (long)max_ij * num)`. Here, `num` acts as `nums[k]`.
- Then, update the maximum difference: `max_ij = max(max_ij, max_i - num)`. Here, `num` acts as `nums[j]`.
- Finally, update the maximum prefix value: `max_i = max(max_i, num)`. Here, `num` acts as `nums[i]`.
- Return `maxVal`.

# Solutions
### Java

```java
class Solution {
public
  long maximumTripletValue(int[] nums) {
    long max, maxDiff, ans;
    max = 0;
    maxDiff = 0;
    ans = 0;
    for (int num : nums) {
      ans = Math.max(ans, num * maxDiff);
      max = Math.max(max, num);
      maxDiff = Math.max(maxDiff, max - num);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumTripletValue(vector<int> &nums) {
    long long ans = 0;
    int mx = 0, mx_diff = 0;
    for (int num : nums) {
      ans = max(ans, 1LL * mx_diff * num);
      mx = max(mx, num);
      mx_diff = max(mx_diff, mx - num);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int: ans = mx = mx_diff = 0 for num in nums: ans = max(ans, mx_diff * num) mx = max(mx, num) mx_diff = max(mx_diff, mx - num) return ans

```