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 <= 1001 <= nums[i] <= 106This approach involves iterating through all possible triplet indices.
We loop through all positions for i, j, and k while maintaining the required i < j < k condition, and for each triplet, we compute the value and maintain the maximum encountered.
While this approach is simple, it's not efficient for large arrays due to its O(n^3) time complexity.
This Python function loops through each combination of i, j, and k, calculates the triplet value, and tracks the maximum value seen.
JavaScript
Time complexity: O(n^3)
Space complexity: O(1)
This approach aims to reduce repetitive calculations by maintaining prefix and suffix arrays.
The idea is to preprocess information to find the maximum elements before and after any element, thereby facilitating quick look-up while iterating through the central elements of the triplets.
This Python solution uses prefix and suffix arrays to maintain the maximum values up to each point. This allows an O(n^2) solution, significantly reducing the time compared to the brute force method.
C++
Time complexity: O(n^2)
Space complexity: O(n)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: O(n^3) |
| Optimized Approach with Prefix and Suffix Arrays | Time complexity: O(n^2) |
Maximum Value of an Ordered Triplet I | Multiple Approaches | Leetcode 2873 | codestorywithMIK • codestorywithMIK • 9,508 views views
Watch 9 more video solutions →Practice Maximum Value of an Ordered Triplet I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor