Skip to content

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

Thinking

A subsequence of length \(m\) has product equal to its first times its last. Fix the right end \(i\); the left end lies at or before \(i-m+1\), so the extreme products use the prefix minimum and maximum.

While scanning, fold \(nums[i-m+1]\) into those extrema and multiply the current \(x\) by both. A negative value can make either extremum optimal.

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
}

Comments