Hard
题目描述
给定一个整数数组 nums 和两个整数 k 和 limit。你的任务是找到 nums 的一个非空子序列，满足：
- 交替和等于
k - 在乘积不超过
limit的前提下，最大化所有数字的乘积
返回满足条件的子序列中数字的乘积。如果没有子序列满足要求，返回 -1。
0 索引数组的交替和定义为偶数索引处元素的和减去奇数索引处元素的和。
示例 1：
输入：nums = [1,2,3], k = 2, limit = 10
输出：6
解释：
交替和为 2 的子序列有：
- [1, 2, 3]：交替和 = 1 - 2 + 3 = 2，乘积 = 1 * 2 * 3 = 6
- [2]：交替和 = 2，乘积 = 2
限制内的最大乘积是 6。
示例 2：
输入：nums = [0,2,3], k = -5, limit = 12
输出：-1
解释：不存在交替和恰好为 -5 的子序列。
示例 3：
输入：nums = [2,2,3,3], k = 0, limit = 9
输出：9
解释：
交替和为 0 的子序列有：
- [2, 2]：交替和 = 2 - 2 = 0，乘积 = 4
- [3, 3]：交替和 = 3 - 3 = 0，乘积 = 9
- [2, 2, 3, 3]：交替和 = 2 - 2 + 3 - 3 = 0，乘积 = 36
子序列 [2, 2, 3, 3] 有最大乘积但超过限制，次大的乘积 9 在限制内。
约束：
1 <= nums.length <= 1500 <= nums[i] <= 12-10^5 <= k <= 10^51 <= limit <= 5000
解题思路
这是一个动态规划问题，需要考虑以下几个要点：
问题分析：
- 我们需要找到交替和等于 k 的子序列，并最大化其乘积
- 交替和意味着子序列中奇数位置的数要加，偶数位置的数要减
- 需要处理乘积为 0 的特殊情况
解题思路：
使用动态规划，状态定义为 dp[sum] = 该交替和下的所有可能乘积集合。
对于每个数字 nums[i]，我们需要考虑两种情况：
- 将其作为新子序列的第一个元素（正号）
- 将其添加到现有子序列中（符号取决于当前长度）
算法步骤：
- 初始化 dp，dp[0] 包含乘积 1（空序列）
- 对于每个数字，更新所有可能的状态
- 需要特别处理数字 0 的情况，因为它会使乘积变为 0
- 最终在 dp[k] 中找到不超过 limit 的最大乘积
优化要点：
- 使用哈希表存储每个和对应的乘积集合
- 对于乘积集合，只保留有用的乘积值（去重并排序）
- 及时剪枝，避免超出 limit 的乘积继续传播
代码实现
class Solution {
public:
int maxProduct(vector<int>& nums, int k, int limit) {
unordered_map<int, set<int>> dp;
dp[0].insert(1);
for (int num : nums) {
unordered_map<int, set<int>> newDp = dp;
for (auto& [sum, products] : dp) {
for (int product : products) {
// Add as positive (start new subsequence or extend with positive)
int newSum1 = sum + num;
long long newProduct1 = (long long)product * num;
if (newProduct1 <= limit) {
newDp[newSum1].insert((int)newProduct1);
}
// Add as negative (extend existing subsequence)
if (product != 1) { // Don't extend empty subsequence with negative
int newSum2 = sum - num;
long long newProduct2 = (long long)product * num;
if (newProduct2 <= limit) {
newDp[newSum2].insert((int)newProduct2);
}
}
}
}
dp = newDp;
}
if (dp.find(k) == dp.end() || dp[k].empty()) {
return -1;
}
return *dp[k].rbegin();
}
};
class Solution:
def maxProduct(self, nums: List[int], k: int, limit: int) -> int:
dp = defaultdict(set)
dp[0].add(1)
for num in nums:
new_dp = defaultdict(set)
for sum_val, products in dp.items():
new_dp[sum_val].update(products)
for sum_val, products in dp.items():
for product in products:
# Add as positive
new_sum1 = sum_val + num
new_product1 = product * num
if new_product1 <= limit:
new_dp[new_sum1].add(new_product1)
# Add as negative (only if not empty subsequence)
if product != 1:
new_sum2 = sum_val - num
new_product2 = product * num
if new_product2 <= limit:
new_dp[new_sum2].add(new_product2)
dp = new_dp
if k not in dp or not dp[k]:
return -1
return max(dp[k])
public class Solution {
public int MaxProduct(int[] nums, int k, int limit) {
var dp = new Dictionary<int, HashSet<int>>();
dp[0] = new HashSet<int> { 1 };
foreach (int num in nums) {
var newDp = new Dictionary<int, HashSet<int>>();
foreach (var kvp in dp) {
if (!newDp.ContainsKey(kvp.Key)) {
newDp[kvp.Key] = new HashSet<int>();
}
foreach (int product in kvp.Value) {
newDp[kvp.Key].Add(product);
}
}
foreach (var kvp in dp) {
int sum = kvp.Key;
var products = kvp.Value;
foreach (int product in products) {
// Add as positive
int newSum1 = sum + num;
long newProduct1 = (long)product * num;
if (newProduct1 <= limit) {
if (!newDp.ContainsKey(newSum1)) {
newDp[newSum1] = new HashSet<int>();
}
newDp[newSum1].Add((int)newProduct1);
}
// Add as negative
if (product != 1) {
int newSum2 = sum - num;
long newProduct2 = (long)product * num;
if (newProduct2 <= limit) {
if (!newDp.ContainsKey(newSum2)) {
newDp[newSum2] = new HashSet<int>();
}
newDp[newSum2].Add((int)newProduct2);
}
}
}
}
dp = newDp;
}
if (!dp.ContainsKey(k) || dp[k].Count == 0) {
return -1;
}
return dp[k].Max();
}
}
var maxProduct = function(nums, k, limit) {
const n = nums.length;
const memo = new Map();
function dfs(index, currentSum, currentProduct, length) {
if (index === n) {
return currentSum === k && length > 0 ? currentProduct : -1;
}
const key = `${index},${currentSum},${currentProduct},${length}`;
if (memo.has(key)) {
return memo.get(key);
}
let result = dfs(index + 1, currentSum, currentProduct, length);
const sign = length % 2 === 0 ? 1 : -1;
const newSum = currentSum + sign * nums[index];
const newProduct = currentProduct * nums[index];
if (newProduct <= limit) {
const withCurrent = dfs(index + 1, newSum, newProduct, length + 1);
result = Math.max(result, withCurrent);
}
memo.set(key, result);
return result;
}
return dfs(0, 0, 1, 0);
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n × S × P)，其中 n 是数组长度，S 是可能的和的数量（最多 2×10^5），P 是每个和对应的乘积数量（最多 limit） |
| 空间复杂度 | O(S × P)，存储所有可能的状态和对应的乘积集合 |