Maximum Product of First and Last Elements of a Subsequence - Solution & Explanation

Problem Overview: You are given an array and must choose a subsequence with at least two elements. The score of the subsequence is the product of its first and last elements. The task is to compute the maximum possible product across all valid subsequences.

The key observation: once the first and last elements are chosen, the elements in between do not affect the score. Any subsequence that starts at index i and ends at index j (with i < j) produces the value nums[i] * nums[j]. The problem reduces to selecting two indices in order that maximize this product.

Approach 1: Brute Force Pair Enumeration (O(n²) time, O(1) space)

Enumerate every pair of indices (i, j) where i < j. Each pair represents a valid subsequence whose first element is nums[i] and last element is nums[j]. Compute the product for every pair and track the maximum value. This approach is straightforward and confirms the core observation that the subsequence interior does not matter. However, it performs n(n-1)/2 comparisons, which becomes too slow for large inputs.

This brute force strategy is useful when first reasoning about the problem, but interviewers expect you to recognize that only prefix values influence the result. Once you fix the last index, you only need the best candidate from the prefix before it.

Approach 2: Enumeration + Maintaining Prefix Extremes (O(n) time, O(1) space)

Iterate through the array while treating each index j as the last element of the subsequence. The first element must come from the prefix [0, j-1]. To maximize the product, the optimal candidate is either the largest value or the smallest value seen so far.

This works because multiplication with a negative number can flip the sign. If nums[j] is positive, pairing it with the maximum prefix value produces the best result. If it is negative, pairing it with the minimum prefix value may create a larger positive product. Maintain two variables while scanning the array: prefixMax and prefixMin. For each index, compute:

max(nums[j] * prefixMax, nums[j] * prefixMin)

Update the global answer, then update the prefix extremes using the current element. This converts the quadratic search into a single linear pass while keeping only constant memory.

This technique appears frequently in array optimization problems and resembles patterns used in maximum product subarray problems. It also aligns with reasoning used in many two pointers or prefix-scanning strategies where you accumulate best candidates from one side of the array.

Recommended for interviews: Start by explaining the brute force pair enumeration to demonstrate understanding of the subsequence definition. Then transition to the prefix-extremes optimization. Interviewers expect the O(n) scan with maintained minimum and maximum prefix values because it shows awareness of sign interactions and efficient array traversal patterns.