3509. Maximum Product of Subsequences With an Alternating Sum Equal to K 

Description

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.

Example 1:

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

Output: 6

Explanation:

The subsequences with an alternating sum of 2 are:

[1, 2, 3]

<ul>
	<li>Alternating Sum: <code>1 - 2 + 3 = 2</code></li>
	<li>Product: <code>1 * 2 * 3 = 6</code></li>
</ul>
</li>
<li><code>[2]</code>
<ul>
	<li>Alternating Sum: 2</li>
	<li>Product: 2</li>
</ul>
</li>

The maximum product within the limit is 6.

Example 2:

Input: nums = [0,2,3], k = -5, limit = 12

Output: -1

Explanation:

A subsequence with an alternating sum of exactly -5 does not exist.

Example 3:

Input: nums = [2,2,3,3], k = 0, limit = 9

Output: 9

Explanation:

The subsequences with an alternating sum of 0 are:

[2, 2]

<ul>
	<li>Alternating Sum: <code>2 - 2 = 0</code></li>
	<li>Product: <code>2 * 2 = 4</code></li>
</ul>
</li>
<li><code>[3, 3]</code>
<ul>
	<li>Alternating Sum: <code>3 - 3 = 0</code></li>
	<li>Product: <code>3 * 3 = 9</code></li>
</ul>
</li>
<li><code>[2, 2, 3, 3]</code>
<ul>
	<li>Alternating Sum: <code>2 - 2 + 3 - 3 = 0</code></li>
	<li>Product: <code>2 * 2 * 3 * 3 = 36</code></li>
</ul>
</li>

The subsequence [2, 2, 3, 3] has the greatest product with an alternating sum equal to k, but 36 > 9. The next greatest product is 9, which is within the limit.

3509. Maximum Product of Subsequences With an Alternating Sum Equal to K 

Description

Solutions

Solution 1

Python3

Java

C++

Go