Difficulty: Easy | Acceptance: 72.60% | Paid: No Topics: Array, Greedy, Sorting, Enumeration
You are given a 0-indexed integer array nums. Find the maximum value of the expression (nums[i] - nums[j]) * nums[k] where 0 <= i < j < k < nums.length.
- Examples
- Constraints
- Brute Force
- Prefix Max and Suffix Max/Min
Examples
Example 1
Input:
nums = [1,4,2,5]
Output:
8
Explanation: We can choose a = 4, b = 5, and c = 1. The expression value is 4 + 5 - 1 = 8, which is the maximum possible.
Example 2
Input:
nums = [-2,0,5,-2,4]
Output:
11
Explanation: We can choose a = 5, b = 4, and c = -2. The expression value is 5 + 4 - (-2) = 11, which is the maximum possible.
Constraints
- 3 <= nums.length <= 100
- -100 <= nums[i] <= 100
Brute Force
Intuition We can check every possible triplet (i, j, k) such that i < j < k and calculate the expression value to find the maximum.
Steps
- Iterate through all possible values of i from 0 to n-3.
- Iterate through all possible values of j from i+1 to n-2.
- Iterate through all possible values of k from j+1 to n-1.
- Calculate the expression (nums[i] - nums[j]) * nums[k] and update the maximum value found.
from typing import List
class Solution:
def maxExpression(self, nums: List[int]) -> int:
n = len(nums)
max_val = float('-inf')
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
current = (nums[i] - nums[j]) * nums[k]
if current > max_val:
max_val = current
return max_val
Complexity
- Time: O(n³)
- Space: O(1)
- Notes: This approach is too slow for the given constraints (n up to 10⁵).
Prefix Max and Suffix Max/Min
Intuition To maximize (nums[i] - nums[j]) * nums[k], we can iterate through the array considering each element as the middle element nums[j]. For a fixed j, we need the maximum nums[i] to its left (to maximize nums[i] - nums[j]) and the best nums[k] to its right. If (nums[i] - nums[j]) is positive, we want the maximum nums[k]. If it is negative, we want the minimum nums[k].
Steps
- Precompute two arrays, suffix_max and suffix_min, where suffix_max[k] stores the maximum value in nums[k..n-1] and suffix_min[k] stores the minimum value in nums[k..n-1].
- Iterate through the array with index j from 1 to n-2.
- Maintain a variable max_left to keep track of the maximum value encountered so far (nums[0..j-1]).
- Calculate diff = max_left - nums[j].
- The potential maximum values for this j are diff * suffix_max[j+1] and diff * suffix_min[j+1]. Update the global maximum result with these values.
from typing import List
class Solution:
def maxExpression(self, nums: List[int]) -> int:
n = len(nums)
suffix_max = [0] * n
suffix_min = [0] * n
suffix_max[-1] = nums[-1]
suffix_min[-1] = nums[-1]
for i in range(n - 2, -1, -1):
suffix_max[i] = max(suffix_max[i + 1], nums[i])
suffix_min[i] = min(suffix_min[i + 1], nums[i])
max_left = nums[0]
res = float('-inf')
for j in range(1, n - 1):
max_left = max(max_left, nums[j - 1])
diff = max_left - nums[j]
if j + 1 < n:
res = max(res, diff * suffix_max[j + 1])
res = max(res, diff * suffix_min[j + 1])
return res
Complexity
- Time: O(n)
- Space: O(n)
- Notes: We use O(n) space to store suffix maximums and minimums. This is optimal for the given constraints.