Maximum Product of Subsequences With an Alternating Sum Equal to K - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3509. Maximum Product of Subsequences With an Alternating Sum Equal to K
Hard
50 Points
Array
Hash Table
Dynamic Programming
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:
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.
Examples
Example 1
Input: nums = [1,2,3], k = 2, limit = 10
Output: 6
Explanation:
The subsequences with an alternating sum of 2 are:
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:
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.
Constraints
1 <= nums.length <= 150
0 <= nums[i] <= 12
-105 <= k <= 105
1 <= limit <= 5000
3509. Maximum Product of Subsequences With an Alternating Sum Equal to K
Hard
50 Points
Array
Hash Table
Dynamic Programming
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:
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.
Examples
Example 1
Input: nums = [1,2,3], k = 2, limit = 10
Output: 6
Explanation:
The subsequences with an alternating sum of 2 are:
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:
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.