Maximum Product of First and Last Elements of a Subsequence Python/Java solution

Python, Java, C++, Go, and TypeScript implementations follow the same logic: iterate through the array, maintain prefixMax and prefixMin, and update the maximum product using nums[j] multiplied by both extremes. The algorithm runs in O(n) time and O(1) space in all languages.

What is the best approach for Maximum Product of First and Last Elements of a Subsequence?

The optimal approach scans the array once while maintaining the maximum and minimum values seen in the prefix. For each index treated as the last element, compute the product with both prefix extremes and update the answer. This enumeration plus prefix-extremes technique runs in O(n) time and O(1) space.

Is Maximum Product of First and Last Elements of a Subsequence asked at Google/Amazon/Meta?

Problems involving maximum product pairs and prefix extreme tracking appear frequently in interviews at companies like Amazon, Google, and Meta. The pattern of maintaining running minimum and maximum values is commonly tested in array optimization questions.

What data structure is used in Maximum Product of First and Last Elements of a Subsequence?

The solution primarily uses simple variables while iterating through an array. Two prefix trackers—maximum and minimum—store the best candidates for the first element of the subsequence. No additional data structures are required beyond constant space variables.

What is the time complexity of Maximum Product of First and Last Elements of a Subsequence?

The optimal solution runs in O(n) time because the array is scanned once while tracking prefix minimum and maximum values. A naive brute force solution checks every pair of indices and takes O(n²) time. Both approaches use O(1) extra space.

3584. Maximum Product of First and Last Elements of a Subsequence - Practice Online

Q: Is Maximum Product of First and Last Elements of a Subsequence easy or hard?

The problem is typically classified as Medium difficulty. The brute force idea is simple, but recognizing that only prefix extremes matter—and handling negative numbers correctly—requires stronger array optimization intuition.

Q: How to solve Maximum Product of First and Last Elements of a Subsequence in O(n)?

Treat each element as the potential last element of the subsequence. Maintain two variables while iterating: the maximum and minimum values seen in the prefix. For every position j, compute nums[j] * prefixMax and nums[j] * prefixMin, update the global maximum, then update the prefix extremes with nums[j].

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