3755. Maximum Product Of First And Last Elements Of A Subsequence¶

3755. Maximum Product of First and Last Elements of a Subsequence

Medium

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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= m <= nums.length

Solution¶

class Solution {
    public long maximumProduct(int[] nums, int m) {
        int n = nums.length;
        int max_pref[] = new int[n];
        int max_suff[] = new int[n];
        int min_pref[] = new int[n];
        int min_suff[] = new int[n];
        max_pref[0] = nums[0];
        min_pref[0] = nums[0];
        for (int i = 1; i < n; i++) {
            max_pref[i] = Math.max(nums[i], max_pref[i - 1]);
            min_pref[i] = Math.min(nums[i], min_pref[i - 1]);
        }
        max_suff[n - 1] = nums[n - 1];
        min_suff[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            max_suff[i] = Math.max(nums[i], max_suff[i + 1]);
            min_suff[i] = Math.min(nums[i], min_suff[i + 1]);
        }
        long res = Long.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int current = nums[i];
            if (current == 0 && (i - m - 1 >= 0 || i + m  - 1 < n))
                res = Math.max(res, 0);
            else if (current < 0) {
                if (i - m - 1 >= 0)
                    res = Math.max(res, current * 1L *  min_pref[i - m - 1]);
                if (i + m - 1 < n)
                    res = Math.max(res, current * 1L * min_suff[i + m - 1]);
            } else if (current > 0) {
                if (i - m - 1 >= 0)
                    res = Math.max(res, current * 1L * max_pref[i - m - 1]);
                if (i + m - 1 < n)
                    res = Math.max(res, current * 1L * max_suff[i + m - 1]);
            }
        }
        return res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]