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

1/**
2 * [3509] Maximum Product of Subsequences With an Alternating Sum Equal to K
3 *
4 * You are given an integer array nums and two integers, k and limit. Your task is to find a non-empty <span data-keyword="subsequence-array">subsequence</span> of nums that:
5 * 
6 * 	Has an alternating sum equal to k.
7 * 	Maximizes the product of all its numbers without the product exceeding limit.
8 * 
9 * Return the product of the numbers in such a subsequence. If no subsequence satisfies the requirements, return -1.
10 * 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.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">nums = [1,2,3], k = 2, limit = 10</span>
15 * Output: <span class="example-io">6</span>
16 * Explanation:
17 * The subsequences with an alternating sum of 2 are:
18 * 
19 * 	[1, 2, 3]
20 * 	
21 * 		Alternating Sum: 1 - 2 + 3 = 2
22 * 		Product: 1 * 2 * 3 = 6
23 * 	
24 * 	
25 * 	[2]
26 * 	
27 * 		Alternating Sum: 2
28 * 		Product: 2
29 * 	
30 * 	
31 * 
32 * The maximum product within the limit is 6.
33 * </div>
34 * <strong class="example">Example 2:
35 * <div class="example-block">
36 * Input: <span class="example-io">nums = [0,2,3], k = -5, limit = 12</span>
37 * Output: <span class="example-io">-1</span>
38 * Explanation:
39 * A subsequence with an alternating sum of exactly -5 does not exist.
40 * </div>
41 * <strong class="example">Example 3:
42 * <div class="example-block">
43 * Input: <span class="example-io">nums = [2,2,3,3], k = 0, limit = 9</span>
44 * Output: <span class="example-io">9</span>
45 * Explanation:
46 * The subsequences with an alternating sum of 0 are:
47 * 
48 * 	[2, 2]
49 * 	
50 * 		Alternating Sum: 2 - 2 = 0
51 * 		Product: 2 * 2 = 4
52 * 	
53 * 	
54 * 	[3, 3]
55 * 	
56 * 		Alternating Sum: 3 - 3 = 0
57 * 		Product: 3 * 3 = 9
58 * 	
59 * 	
60 * 	[2, 2, 3, 3]
61 * 	
62 * 		Alternating Sum: 2 - 2 + 3 - 3 = 0
63 * 		Product: 2 * 2 * 3 * 3 = 36
64 * 	
65 * 	
66 * 
67 * 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.
68 * </div>
69 *  
70 * Constraints:
71 * 
72 * 	1 <= nums.length <= 150
73 * 	0 <= nums[i] <= 12
74 * 	-10^5 <= k <= 10^5
75 * 	1 <= limit <= 5000
76 * 
77 */
78pub struct Solution {}
79
80// problem: https://leetcode.com/problems/maximum-product-of-subsequences-with-an-alternating-sum-equal-to-k/
81// discuss: https://leetcode.com/problems/maximum-product-of-subsequences-with-an-alternating-sum-equal-to-k/discuss/?currentPage=1&orderBy=most_votes&query=
82
83// submission codes start here
84
85impl Solution {
86    pub fn max_product(nums: Vec<i32>, k: i32, limit: i32) -> i32 {
87        0
88    }
89}
90
91// submission codes end
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96
97    #[test]
98    fn test_3509() {
99    }
100}
101