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: 3

💡 Note: Choose subsequence [1,3] where first=1, last=3, product = 1×3 = 3. 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

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

✓ Brute Force - Generate All Subsequences

⏱️ Time: O(C(n,m) × m) Space: O(m)

Try every possible combination of m elements from the array. For each valid subsequence, calculate the product of its first and last elements and track the maximum.

Optimized Two-Pass Approach

⏱️ Time: O(n²) Space: O(1)

Instead of generating all combinations, iterate through each element as a potential first element. For each first element, find the best last element from the remaining positions that maintain a subsequence of size m.

Two Pointers with Preprocessing

⏱️ Time: O(n²) Space: O(n)

Preprocess the array to find the maximum and minimum values in different segments. Then use two pointers to efficiently find the maximum product by considering both positive and negative products.

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all combinations of m elements
For each combination, calculate first × last
Return the maximum product found

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

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

Generate

Create all combinations of 3 elements

Calculate

Find first×last for each combination

Code -

solution.c — C

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

long long maxProduct;

void generateCombinations(int* nums, int numsSize, int m, int start, int* current, int currentSize) {
    if (currentSize == m) {
        long long product = (long long)current[0] * current[currentSize - 1];
        if (product > maxProduct) {
            maxProduct = product;
        }
        return;
    }
    
    for (int i = start; i < numsSize; i++) {
        current[currentSize] = nums[i];
        generateCombinations(nums, numsSize, m, i + 1, current, currentSize + 1);
    }
}

long long solution(int* nums, int numsSize, int m) {
    maxProduct = LLONG_MIN;
    int* current = (int*)malloc(m * sizeof(int));
    generateCombinations(nums, numsSize, m, 0, current, 0);
    free(current);
    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(C(n,m) × m)

Generate C(n,m) combinations, each taking O(m) time to process

⚠ Quadratic Growth

Space Complexity

O(m)

Store current subsequence of size m

⚡ Linearithmic 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler