Problem Summary

You are given an integer array nums.

You must choose three indices i < j < k such that the value

(nums[i] - nums[j]) * nums[k]

is maximized.

Return the maximum possible value of this expression.

Constraints

• 3 ≤ nums.length ≤ 1000
• 1 ≤ nums[i] ≤ 10⁶
• A brute force O(n³) would be too slow; O(n²) or better is needed.

---

Understanding the Expression

We want to maximize:

(nums[i] - nums[j]) * nums[k]

The constraints are:

1. i < j < k
2. nums[k] is multiplied with the difference (nums[i] - nums[j])

Important Observations

If (nums[i] - nums[j]) is negative, multiplying with positive nums[k] reduces the answer.
So ideally we want:

• nums[i] as large as possible before j
• nums[j] as small as possible
• nums[k] as large as possible after j

This naturally suggests a middle index j that splits the triplet.

---

Approach (Simple English)

The expression depends on three parts, separated by j:

1. Best nums[i] before j
2. nums[j]
3. Best nums[k] after j

We can preprocess:

• leftMax[i] = maximum number in nums[0..i−1]
• rightMax[i] = maximum number in nums[i+1..n−1]

Then for each middle index j, compute:

value = (leftMax[j] - nums[j]) * rightMax[j]

Take the maximum over all j.

Why This Works

At each j:

• The best candidate for i is the largest element before j
• The best candidate for k is the largest element after j

This yields the maximum possible value for each fixed j.

Time complexity becomes O(n).

---

Steps

1. Build prefix max array: leftMax
2. Build suffix max array: rightMax
3. Loop j from 1 to n−2
4. Compute value: (leftMax[j] - nums[j]) * rightMax[j]
5. Track the maximum

---

Java Code (Optimal O(n) Solution)

class Solution {
    public long maximumTripletValue(int[] nums) {

        int n = nums.length;
        long maxValue = 0;

        // Step 1: prefix max
        int[] leftMax = new int[n];
        leftMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
        }

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

        // Step 3: evaluate all possible j
        for (int j = 1; j < n - 1; j++) {
            long left = leftMax[j];
            long mid = nums[j];
            long right = rightMax[j];

            long value = (left - mid) * right;
            if (value > maxValue) {
                maxValue = value;
            }
        }

        return maxValue;
    }
}

---

Dry Run

Input:

nums = [12, 6, 1, 2, 7]

Step 1: leftMax

leftMax = [12, 12, 6, 1, 2]   // max before each index

Step 2: rightMax

rightMax = [7, 7, 7, 7, 7]    // max after each index

Step 3: Iterate j from 1 to 3

For j = 1 (nums[j] = 6):

(12 - 6) * 7 = 6 * 7 = 42
maxValue = 42

For j = 2 (nums[j] = 1):

(12 - 1) * 7 = 11 * 7 = 77
maxValue = 77

For j = 3 (nums[j] = 2):

(6 - 2) * 7 = 4 * 7 = 28
maxValue stays 77

Final answer = 77

---

Complexity Analysis

Time Complexity:
O(n) for prefix max + suffix max + single loop.

Space Complexity:
O(n) for leftMax and rightMax arrays.

---

Edge Cases

• Strictly increasing array
  Best i is always at the left, best k at the right.
• All equal numbers
  Differences become zero → answer is zero.
• nums[j] is the largest among the three
  Differences become negative → expression becomes small or zero.