2909. Minimum Sum of Mountain Triplets II

T: O(n)

S: O(n)

```java
class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        // leftMax[i] is the current max value before i index
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], nums[i-1]);
        }
        // vice versa
        for (int i = n-2; i >=0 ; i--) {
            rightMax[i] = Math.max(rightMax[i+1], nums[i+1]);
        }

        long result = 0;
        // as nums[j] (1 to n-2, 0 is nums[i], n-1 is nums[k]) as the center to use MaxLeft, Maxright to calculate
        for (int i = 1; i < n-1; i++) {
            result = Math.max(result, (long)(leftMax[i] - nums[i])*rightMax[i]);
        }
        return result;
    }
}
```

Last updated