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.

Description Hints 2 Solution Video 20:29

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

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].

Medium31.9% acceptance1 company

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

Asked at 1 company

KLA

Topics

Array Two Pointers

Hints open one at a time

Hint 1

We can select nums[i] as the first element of the subsequence, and the last one can be any of nums[i + m - 1], nums[i + m], ..., nums[n - 1].

Hint 2

If we select the first element from the largest i, the suffix just gets longer, and we can update the minimum and maximum values dynamically.

20:29

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maximumProduct(self, nums: List[int], m: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[-1,-9,2,3,-2,-3,1]
1

Input

[1,3,-5,5,6,-4]
3

Input

[2,-1,2,-6,5,2,-5,7]
2

Your code is saved on this device.Solution