Maximum Product of Subsequences With an Alternating Sum Equal to K

Maximum Product of Subsequences With an Alternating Sum Equal to K - Problem

You are given an integer array nums and two integers, k and limit. Your task is to find a non-empty subsequence of nums that:

Has an alternating sum equal to k
Maximizes the product of all its numbers without the product exceeding limit

Return the product of the numbers in such a subsequence. If no subsequence satisfies the requirements, return -1.

The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,1,4], k = 5, limit = 100

› Output: 6

💡 Note: Subsequence [2,3] has alternating sum 2-3=-1+3=2, wait... [2,3] at positions 0,1 gives 2-3=-1. Actually [3,1] at positions 1,2 gives 3-1=2. Let me recalculate: [2,1] gives 2-1=1, [3,4] gives 3-4=-1. Actually subsequence [2,3,1] gives 2-3+1=0. Need to find sum=5: [2,3] is 2-3=-1, [3,1,4] is 3-1+4=6≠5. Let me try [2,1,4]: 2-1+4=5 ✓, product=2×1×4=8. But there might be [3,4] giving 3-4=-1≠5. Actually [4,3] would be 4-3=1≠5. So [1,4] gives 1-4=-3≠5. Hmm, let me try [2,3,4]: 2-3+4=3≠5. [3,1]: 3-1=2≠5. Wait, [2,3]: alt sum is 2-3=-1≠5. Let me try [1,4]: 1-4=-3. Hmm. Actually, maybe [3,4]: 3-4=-1. Let me systematically check: single elements don't work. [2,3]: 2-3=-1. [2,1]: 2-1=1. [2,4]: 2-4=-2. [3,1]: 3-1=2. [3,4]: 3-4=-1. [1,4]: 1-4=-3. For 3 elements: [2,3,1]: 2-3+1=0. [2,3,4]: 2-3+4=3. [2,1,4]: 2-1+4=5 ✓ (product=8). [3,1,4]: 3-1+4=6. All 4: [2,3,1,4]: 2-3+1-4=-4. So [2,1,4] gives sum=5, product=8. But wait, we also need to check if there are other valid subsequences with sum=5 and higher product.

Example 2 — No Valid Solution

$ Input: nums = [1,2,3], k = 10, limit = 20

› Output: -1

💡 Note: No subsequence can achieve alternating sum = 10. Max possible is [1,2,3] = 1-2+3 = 2

Example 3 — Limit Constraint

$ Input: nums = [5,2,4], k = 3, limit = 8

› Output: -1

💡 Note: Subsequence [5,2] has sum 5-2=3, but product 5×2=10 exceeds limit 8

Constraints

1 ≤ nums.length ≤ 20
-10⁶ ≤ nums[i] ≤ 10⁶
-10⁶ ≤ k ≤ 10⁶
1 ≤ limit ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,3,1,4], target sum k=5, limit=100

Process

Find subsequences with alternating sum = 5

Output

Return maximum product ≤ limit

Key Takeaway

🎯 Key Insight: Use backtracking to explore all subsequences while tracking both alternating sum and product constraints

Asked in

G Google 25 M Microsoft 18

This problem requires finding a subsequence with specific alternating sum while maximizing product under a constraint. The key insight is to use backtracking with pruning to explore all valid combinations efficiently. Best approach is memoized recursion. Time: O(2ⁿ), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Subsequences	O(n × 2ⁿ)	O(n)	Generate all possible subsequences and check each one
Dynamic Programming with Memoization	O(n × k × limit)	O(n × k × limit)	Use recursion with memoization to explore valid subsequences

Generate All Subsequences — Algorithm Steps

Generate all 2^n possible subsequences
For each subsequence, calculate alternating sum and product
Keep track of maximum valid product

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible subsequences using bitmask

Check

Calculate alternating sum and product for each

Select

Find maximum valid product

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int k, int limit) {
    int maxProduct = -1;
    
    // Generate all subsequences using bit manipulation
    for (int mask = 1; mask < (1 << numsSize); mask++) {
        int subsequence[20];
        int subSize = 0;
        
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                subsequence[subSize++] = nums[i];
            }
        }
        
        // Calculate alternating sum
        int altSum = 0;
        for (int i = 0; i < subSize; i++) {
            if (i % 2 == 0) {
                altSum += subsequence[i];
            } else {
                altSum -= subsequence[i];
            }
        }
        
        // Check if alternating sum equals k
        if (altSum == k) {
            // Calculate product
            long long product = 1;
            for (int i = 0; i < subSize; i++) {
                product *= subsequence[i];
            }
            
            // Check if product is within limit and update max
            if (product <= limit) {
                if (product > maxProduct) {
                    maxProduct = (int)product;
                }
            }
        }
    }
    
    return maxProduct;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || strcmp(token, "0") == 0) {
            nums[numsSize++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int k, limit;
    scanf("%d", &k);
    scanf("%d", &limit);
    
    int result = solution(nums, numsSize, k, limit);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ)

Generate 2^n subsequences, each taking O(n) time to process

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth and temporary subsequence storage

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

420 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

Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler