给你一个长度为 n 的整数数组 nums ,和一个长度为 m 的整数数组 queries 。 返回一个长度为 m 的数组 answer ,其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。 子序列 是由一个数组删除某些元素(也可以不删除)但不改变剩余元素顺序得到的一个数组。 java代码
时间: 2024-03-21 12:39:15 浏览: 248
好的,以下是 Java 代码实现:
```java
public int[] maxSubArrayLen(int[] nums, int[] queries) {
int n = nums.length, m = queries.length;
int[][] dp = new int[n+1][100001]; // dp数组,第二维大小为 nums 数组元素之和的最大值加一
int[] presum = new int[n+1]; // nums 数组的前缀和
int[] ans = new int[m];
// 计算 nums 数组的前缀和
for (int i = 1; i <= n; i++) {
presum[i] = presum[i-1] + nums[i-1];
}
// 填充 dp 数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= presum[i]; j++) {
dp[i][j] = dp[i-1][j]; // 不选第 i 个数
if (presum[i] - presum[i-1] <= j) { // 选第 i 个数
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-(presum[i]-presum[i-1])] + 1);
}
}
}
// 计算答案数组
for (int i = 0; i < m; i++) {
int q = queries[i];
if (q >= presum[n]) { // 如果 queries[i] 大于等于 nums 数组的元素和,答案为 nums 数组的长度
ans[i] = n;
} else { // 否则在 dp 数组中查找最大长度
ans[i] = 0;
for (int j = 1; j <= q; j++) {
ans[i] = Math.max(ans[i], dp[n][j]);
}
}
}
return ans;
}
```
这里 dp 数组的第二维大小为 nums 数组元素之和的最大值加一,是为了防止数组越界。同时,如果 queries[i] 大于等于 nums 数组的元素和,答案为 nums 数组的长度,因为此时可以选择全部元素组成子序列。
阅读全文