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,1,4], k = 5, limit = 100

› Output: 8

💡 Note: Subsequence [2,1,4] has alternating sum 2-1+4=5 and product 2×1×4=8

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

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

✓ Dynamic Programming with Memoization

⏱️ Time: O(n × k × limit) Space: O(n × k × limit)

Recursively explore all possible subsequences while memoizing results. For each position, decide whether to include or exclude the element, tracking alternating sum and product constraints.

Generate All Subsequences

⏱️ Time: O(n × 2ⁿ) Space: O(n)

Generate every possible subsequence, calculate its alternating sum and product, then find the maximum valid product that equals k and doesn't exceed limit.

Dynamic Programming with Memoization — Algorithm Steps

Use recursion to explore include/exclude decisions
Track current alternating sum and position
Memoize results to avoid recomputation
Prune branches that exceed constraints

Visualization

Tap to expand

Step-by-Step Walkthrough

Recurse

For each element, try include/exclude

Track

Monitor alternating sum and product

Prune

Skip branches exceeding limits

Code -

solution.c — C

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

long long maxProduct = -1;

long long llabs(long long x) {
    return x < 0 ? -x : x;
}

long long max_ll(long long a, long long b) {
    return a > b ? a : b;
}

void backtrack(int* nums, int numsSize, int index, int currentSum, int seqLen, long long currentProduct, int k, int limit) {
    if (index == numsSize) {
        if (seqLen > 0 && currentSum == k && llabs(currentProduct) <= limit) {
            maxProduct = max_ll(maxProduct, currentProduct);
        }
        return;
    }
    
    // Skip current element
    backtrack(nums, numsSize, index + 1, currentSum, seqLen, currentProduct, k, limit);
    
    // Include current element
    long long newProduct = seqLen > 0 ? currentProduct * nums[index] : nums[index];
    if (llabs(newProduct) <= 1000000000000000000LL) { // Avoid overflow
        int newSum = seqLen % 2 == 0 ? currentSum + nums[index] : currentSum - nums[index];
        backtrack(nums, numsSize, index + 1, newSum, seqLen + 1, newProduct, k, limit);
    }
}

int solution(int* nums, int numsSize, int k, int limit) {
    maxProduct = -1;
    backtrack(nums, numsSize, 0, 0, 0, 1, k, limit);
    return maxProduct == -1 ? -1 : (int)maxProduct;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[20];
    int numsSize = 0;
    char* ptr = line + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        while (*ptr && (*ptr == ' ' || *ptr == ',')) ptr++;
        if (*ptr && *ptr != ']') {
            nums[numsSize++] = atoi(ptr);
            while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        }
    }
    
    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 × k × limit)

Each unique state (position, sum, sign) is computed once

✓ Linear Growth

Space Complexity

O(n × k × limit)

Memoization table stores results for all possible states

⚡ 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler