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:
k.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]
1 - 2 + 3 = 21 * 2 * 3 = 6[2]
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]
2 - 2 = 02 * 2 = 4[3, 3]
3 - 3 = 03 * 3 = 9[2, 2, 3, 3]
2 - 2 + 3 - 3 = 02 * 2 * 3 * 3 = 36The 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 <= 1500 <= nums[i] <= 12-105 <= k <= 1051 <= limit <= 5000