# Maximum Value of an Ordered Triplet II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-value-of-an-ordered-triplet-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-value-of-an-ordered-triplet-ii
**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 <= 105`
* `1 <= nums[i] <= 106`

# Approaches
## Brute Force with Three Nested Loops
The most straightforward approach is to use brute force. We can generate every possible ordered triplet of indices `(i, j, k)` where `i < j < k`, calculate the value `(nums[i] - nums[j]) * nums[k]` for each triplet, and keep track of the maximum value found. We initialize our maximum value to 0, as the problem states to return 0 if all triplet values are negative.
**Time:** O(N^3) - Where N is the length of the `nums` array. The three nested loops lead to a cubic time complexity, which is too slow for N up to 10^5. · **Space:** O(1) - Constant extra space is used, as we only need a few variables to store the loop indices and the maximum value.
**Pros:** Simple to understand and implement.; Correct for small input sizes.
**Cons:** Extremely inefficient for large inputs.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
### Explanation
This method involves three nested loops. The first loop iterates through the index `i` from the beginning of the array. The second loop iterates through `j` starting from `i + 1`, and the third loop iterates through `k` starting from `j + 1`. This ensures that we only consider valid ordered triplets `(i < j < k)`. For each triplet, we compute its value and update our overall maximum. Using a `long` for the result is crucial to avoid integer overflow, as the product can exceed the capacity of a standard 32-bit integer.

```java
class Solution {
    public long maximumValueSum(int[] nums) {
        int n = nums.length;
        long maxValue = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    long currentValue = (long)(nums[i] - nums[j]) * nums[k];
                    if (currentValue > maxValue) {
                        maxValue = currentValue;
                    }
                }
            }
        }

        return maxValue;
    }
}
```
### Algorithm
1. Initialize a variable `maxValue` to 0, using a `long` data type to prevent potential overflow.
2. Use three nested loops to iterate through all possible combinations of indices `(i, j, k)` such that `i < j < k`.
   - The outer loop for `i` runs from `0` to `n-3`.
   - The middle loop for `j` runs from `i+1` to `n-2`.
   - The inner loop for `k` runs from `j+1` to `n-1`.
3. Inside the innermost loop, calculate the value of the triplet: `currentValue = (long)(nums[i] - nums[j]) * nums[k]`.
4. Compare `currentValue` with `maxValue` and update `maxValue` if `currentValue` is greater: `maxValue = Math.max(maxValue, currentValue)`.
5. After the loops complete, `maxValue` will hold the maximum possible value. Since the problem asks to return 0 for negative results, and our `maxValue` is initialized to 0 and only updated with larger values, this condition is naturally met.
6. Return `maxValue`.

## Optimized Approach with Precomputation
We can significantly improve the time complexity by avoiding the innermost loop. If we fix the middle index `j`, our goal is to find the maximum `nums[i]` for all `i < j` and the maximum `nums[k]` for all `k > j`. Instead of recalculating these maximums for each `j`, we can precompute them in linear time.
**Time:** O(N) - We make three separate passes through the array (one for prefix max, one for suffix max, and one for the final calculation), each taking linear time. Thus, the total time complexity is O(N) + O(N) + O(N) = O(N). · **Space:** O(N) - We use two additional arrays, `prefixMax` and `suffixMax`, each of size N.
**Pros:** Significantly more time-efficient than the brute-force approach.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Requires extra space proportional to the input size, which might be a concern for very large arrays in memory-constrained environments.
### Explanation
This approach involves two main steps. First, we perform two passes over the array to create helper arrays. The `prefixMax` array is built from left to right, where `prefixMax[i] = max(prefixMax[i-1], nums[i])`. The `suffixMax` array is built from right to left, where `suffixMax[i] = max(suffixMax[i+1], nums[i])`. 

After precomputation, we iterate through the array a final time, considering each element `nums[j]` (for `1 <= j <= n-2`) as the middle element of the triplet. For each `j`, we can find the required maximums `max(nums[i])` and `max(nums[k])` in O(1) time using our precomputed arrays. This reduces the overall time complexity to be linear.

```java
class Solution {
    public long maximumValueSum(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 maxValue = 0;
        for (int j = 1; j < n - 1; j++) {
            long val_i = prefixMax[j - 1];
            long val_k = suffixMax[j + 1];
            long currentValue = (val_i - nums[j]) * val_k;
            if (currentValue > maxValue) {
                maxValue = currentValue;
            }
        }

        return maxValue;
    }
}
```
### Algorithm
1. The goal is to maximize `(nums[i] - nums[j]) * nums[k]`.
2. For a fixed middle index `j`, the value is maximized when `nums[i]` (for `i < j`) is as large as possible and `nums[k]` (for `k > j`) is as large as possible (since `nums[k]` is positive).
3. We can precompute the maximum values for all prefixes and suffixes of the array.
4. Create a `prefixMax` array of size `n`, where `prefixMax[i]` stores the maximum value in `nums[0...i]`.
5. Create a `suffixMax` array of size `n`, where `suffixMax[i]` stores the maximum value in `nums[i...n-1]`.
6. Initialize `maxValue = 0L`.
7. Iterate with a single loop for `j` from `1` to `n-2`.
8. For each `j`, the maximum `nums[i]` for `i < j` is `prefixMax[j-1]`, and the maximum `nums[k]` for `k > j` is `suffixMax[j+1]`.
9. Calculate the potential maximum for this `j`: `currentValue = (long)(prefixMax[j-1] - nums[j]) * suffixMax[j+1]`.
10. Update the overall maximum: `maxValue = Math.max(maxValue, currentValue)`.
11. Return `maxValue`.

## Optimal Single Pass Solution
The most optimal solution improves upon the previous approach by eliminating the need for extra space. We can achieve O(1) space complexity by calculating the necessary maximums on the fly within a single pass. The key idea is to iterate through the array and, for each potential third element `nums[k]`, find the best possible `(nums[i] - nums[j])` part from the elements that appeared before it.
**Time:** O(N) - We iterate through the array only once, performing constant time operations at each step. · **Space:** O(1) - This approach uses only a few variables to store the running maximums, regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Most efficient solution for the given problem.
**Cons:** The logic can be less intuitive to grasp compared to the precomputation method.
### Explanation
We iterate through the array from left to right, maintaining two key variables. The first, `max_i_val`, keeps track of the maximum element value encountered so far, which represents the best possible `nums[i]`. The second, `max_prefix_diff`, tracks the maximum difference `(nums[i] - nums[j])` found so far.

As we iterate with index `j` from `1` to `n-2`, we treat `nums[j]` as a potential middle element. We update `max_prefix_diff` using the current `max_i_val` and `nums[j]`. Then, we consider `nums[j+1]` as a potential third element `nums[k]` and calculate a candidate for the maximum triplet value by multiplying it with the current `max_prefix_diff`. Finally, we update `max_i_val` to include `nums[j]` before proceeding to the next iteration. This dynamic programming approach ensures we find the maximum value in a single pass with constant extra space.

```java
class Solution {
    public long maximumValueSum(int[] nums) {
        int n = nums.length;
        long ans = 0;
        
        // max_i_val will store the maximum of nums[i] for i < j
        int max_i_val = nums[0];
        // max_prefix_diff will store the maximum of (nums[i] - nums[j]) for i < j
        int max_prefix_diff = 0;

        // We iterate j from 1 to n-2. In each iteration, we consider nums[j+1] as nums[k].
        for (int j = 1; j < n - 1; j++) {
            // Update the maximum possible difference (nums[i] - nums[j]) found so far.
            // For the current nums[j], the best nums[i] is the max value before it (max_i_val).
            max_prefix_diff = Math.max(max_prefix_diff, max_i_val - nums[j]);
            
            // The current max_prefix_diff is the best (nums[a] - nums[b]) for a < b <= j.
            // We can pair this with nums[j+1] as our nums[k].
            ans = Math.max(ans, (long)max_prefix_diff * nums[j + 1]);
            
            // Update max_i_val to include nums[j] for the next iteration.
            max_i_val = Math.max(max_i_val, nums[j]);
        }

        return ans;
    }
}
```
### Algorithm
1. The expression to maximize is `(nums[i] - nums[j]) * nums[k]`.
2. We can iterate through the array and at each position `p`, consider `nums[p]` as `nums[k]`. To get the max value, we need to multiply `nums[p]` by the maximum possible value of `(nums[i] - nums[j])` where `i < j < p`.
3. We can find this maximum `(nums[i] - nums[j])` part iteratively in a single pass.
4. Initialize `ans = 0L`, `max_i_val = nums[0]`, and `max_prefix_diff = 0`.
   - `max_i_val` will track the maximum `nums[i]` seen so far.
   - `max_prefix_diff` will track the maximum `(nums[i] - nums[j])` seen so far.
5. Iterate `j` from `1` to `n-2`.
6. In each iteration, `max_i_val` holds the maximum value in `nums[0...j-1]`. We can form a new potential difference `max_i_val - nums[j]`. Update `max_prefix_diff = Math.max(max_prefix_diff, max_i_val - nums[j])`.
7. Now, `max_prefix_diff` holds the maximum possible value for `(nums[a] - nums[b])` where `a < b <= j`. The element `nums[j+1]` can serve as our `nums[k]`.
8. Calculate a potential answer: `ans = Math.max(ans, (long)max_prefix_diff * nums[j+1])`.
9. Before the next iteration, update `max_i_val` to include the current element: `max_i_val = Math.max(max_i_val, nums[j])`.
10. Return `ans`.

# 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

```