Maximum Product of Subsequences With an Alternating Sum Equal to K
You are given an integer array nums and two integers, k and limit.
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.
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
- -10^5 <= k <= 10^5
- 1 <= limit <= 5000
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.