Maximum Product of First and Last Elements of a Subsequence

Maximum Product of First and Last Elements of a Subsequence - Problem

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.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,-4,3,5,2], m = 3

› Output: 5

💡 Note: Choose subsequence [1,3,5] where first=1, last=5, product = 1×5 = 5. Or choose [1,5,2] where first=1, last=2, product = 1×2 = 2. The maximum is 5.

Example 2 — Negative Numbers

$ Input: nums = [-2,1,3,-1], m = 2

› Output: 2

💡 Note: Choose subsequence [-2,-1] where first=-2, last=-1, product = (-2)×(-1) = 2. This gives the maximum product among all possible subsequences of size 2.

Example 3 — Same Elements

$ Input: nums = [4,4,4,4], m = 3

› Output: 16

💡 Note: Any subsequence of size 3 will have first=4 and last=4, so the product is 4×4 = 16.

Constraints

2 ≤ nums.length ≤ 10⁴
2 ≤ m ≤ nums.length
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,-4,3,5,2] with m=3

Process

Find all valid subsequences of size 3

Output

Maximum product of first×last = 5

Key Takeaway

🎯 Key Insight: Only the first and last elements matter in the product calculation, so we can efficiently check all valid first-last pairs instead of generating complete subsequences.

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that we only care about the first and last elements of the subsequence, so we can try all valid first-last pairs. The optimized approach uses nested loops to check each possible first element with all valid last elements. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Two-Pass Approach	O(n²)	O(1)	For each possible first element, find the optimal last element
Brute Force - Generate All Subsequences	O(C(n,m) × m)	O(m)	Generate all possible subsequences of size m and find maximum product
Two Pointers with Preprocessing	O(n²)	O(n)	Use preprocessing to find maximum products efficiently with two pointers

Optimized Two-Pass Approach — Algorithm Steps

For each element i as first element
Consider all valid positions j for last element (j >= i + m - 1)
Calculate product nums[i] × nums[j] and track maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose First

Select element at position i as first

Find Last

Try all valid positions j >= i+m-1 as last

Calculate

Compute nums[i] × nums[j] for maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long solution(int* nums, int numsSize, int m) {
    long long maxProduct = LLONG_MIN;
    
    // Try each element as the first element
    for (int i = 0; i <= numsSize - m; i++) {
        // Try each valid element as the last element
        for (int j = i + m - 1; j < numsSize; j++) {
            long long product = (long long)nums[i] * nums[j];
            if (product > maxProduct) {
                maxProduct = product;
            }
        }
    }
    
    return maxProduct;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int m;
    scanf("%d", &m);
    
    long long result = solution(nums, numsSize, m);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop n iterations, inner loop up to n iterations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Two-Pass Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler