is 0 (even length) or 1 (odd length).

Initialize with an empty state: dp[0][0] = 1 (product 1 for sum 0, even length).

For each number in nums, for each state in dp, try to add the number to the subsequence:

If current parity is p, next parity is 1-p.
If next parity is odd, add the number to the alternating sum; if even, subtract it.
Multiply the product, but only keep it if it does not exceed limit.
Update the DP for the new state if the product is better.

After processing all numbers, the answer is the maximum product for dp[parity][k] (for any parity), but only if the product is ≤ limit and the subsequence is non-empty.

If no such subsequence exists, return -1.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maximumProduct(vector<int>& nums, int k, int limit) {\n        unordered_map<int, unordered_map<int, int>> dp[2];\n        dp[0][0][1] = 1;\n        for (int x : nums) {\n            auto old = dp;\n            for (int p = 0; p < 2; ++p) {\n                for (auto& [s, m] : old[p]) {\n                    for (auto& [prod, _] : m) {\n                        int np = 1 - p;\n                        int ns = (np ? s + x : s - x);\n                        long long nprod = 1LL * prod * x;\n                        if (nprod > limit) continue;\n                        dp[np][ns][nprod] = max(dp[np][ns][nprod], (int)nprod);\n                    }\n                }\n            }\n        }\n        int ans = -1;\n        for (int p = 0; p < 2; ++p) {\n            for (auto& [prod, _] : dp[p][k]) {\n                if (prod <= limit) ans = max(ans, prod);\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\">

Related Tags