Welcome to Subscribe On Youtube
3584. Maximum Product of First and Last Elements of a Subsequence
Description
You are given an integer array nums
and an integer m
.
Return the maximum product of the first and last elements of any subsequence of nums
of size m
.
Example 1:
Input: nums = [-1,-9,2,3,-2,-3,1], m = 1
Output: 81
Explanation:
The subsequence [-9]
has the largest product of the first and last elements: -9 * -9 = 81
. Therefore, the answer is 81.
Example 2:
Input: nums = [1,3,-5,5,6,-4], m = 3
Output: 20
Explanation:
The subsequence [-5, 6, -4]
has the largest product of the first and last elements.
Example 3:
Input: nums = [2,-1,2,-6,5,2,-5,7], m = 2
Output: 35
Explanation:
The subsequence [5, 7]
has the largest product of the first and last elements.
Constraints:
1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= m <= nums.length
Solutions
Solution 1: Enumeration + Maintaining Prefix Extremes
We can enumerate the last element of the subsequence, assuming it is $\textit{nums}[i]$. Then the first element of the subsequence can be $\textit{nums}[j]$, where $j \leq i - m + 1$. Therefore, we use two variables $\textit{mi}$ and $\textit{mx}$ to maintain the prefix minimum and maximum values respectively. When traversing to $\textit{nums}[i]$, we update $\textit{mi}$ and $\textit{mx}$, then calculate the products of $\textit{nums}[i]$ with $\textit{mi}$ and $\textit{mx}$, taking the maximum value.
The time complexity is $O(n)$, where $n$ is the length of array $\textit{nums}$. And the space complexity is $O(1)$.
-
class Solution { public long maximumProduct(int[] nums, int m) { long ans = Long.MIN_VALUE; int mx = Integer.MIN_VALUE; int mi = Integer.MAX_VALUE; for (int i = m - 1; i < nums.length; ++i) { int x = nums[i]; int y = nums[i - m + 1]; mi = Math.min(mi, y); mx = Math.max(mx, y); ans = Math.max(ans, Math.max(1L * x * mi, 1L * x * mx)); } return ans; } }
-
class Solution { public: long long maximumProduct(vector<int>& nums, int m) { long long ans = LLONG_MIN; int mx = INT_MIN; int mi = INT_MAX; for (int i = m - 1; i < nums.size(); ++i) { int x = nums[i]; int y = nums[i - m + 1]; mi = min(mi, y); mx = max(mx, y); ans = max(ans, max(1LL * x * mi, 1LL * x * mx)); } return ans; } };
-
class Solution: def maximumProduct(self, nums: List[int], m: int) -> int: ans = mx = -inf mi = inf for i in range(m - 1, len(nums)): x = nums[i] y = nums[i - m + 1] mi = min(mi, y) mx = max(mx, y) ans = max(ans, x * mi, x * mx) return ans
-
func maximumProduct(nums []int, m int) int64 { ans := int64(math.MinInt64) mx := math.MinInt32 mi := math.MaxInt32 for i := m - 1; i < len(nums); i++ { x := nums[i] y := nums[i-m+1] mi = min(mi, y) mx = max(mx, y) ans = max(ans, max(int64(x)*int64(mi), int64(x)*int64(mx))) } return ans }
-
function maximumProduct(nums: number[], m: number): number { let ans = Number.MIN_SAFE_INTEGER; let mx = Number.MIN_SAFE_INTEGER; let mi = Number.MAX_SAFE_INTEGER; for (let i = m - 1; i < nums.length; i++) { const x = nums[i]; const y = nums[i - m + 1]; mi = Math.min(mi, y); mx = Math.max(mx, y); ans = Math.max(ans, x * mi, x * mx); } return ans; }