class Solution {
public:
int lengthOfLongestSubsequence(vector<int>& nums, int target) {
}
};
100042. 和为目标值的最长子序列的长度
给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。
子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。
示例 1：
输入：nums = [1,2,3,4,5], target = 9 输出：3 解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。
示例 2：
输入：nums = [4,1,3,2,1,5], target = 7 输出：4 解释：总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。最长子序列为 [1,3,2,1] 。所以答案为 4 。
示例 3：
输入：nums = [1,1,5,4,5], target = 3 输出：-1 解释：无法得到和为 3 的子序列。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 10001 <= target <= 1000原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 5.4 MB, 提交时间: 2023-10-29 10:41:59
func lengthOfLongestSubsequence(nums []int, target int) int {
f := make([]int, target+1)
for i := 1; i <= target; i++ {
f[i] = math.MinInt
}
s := 0
for _, x := range nums {
s = min(s+x, target)
for j := s; j >= x; j-- {
f[j] = max(f[j], f[j-x]+1)
}
}
if f[target] > 0 {
return f[target]
}
return -1
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 140 ms, 内存消耗: 28.5 MB, 提交时间: 2023-10-29 10:41:47
class Solution {
public:
int lengthOfLongestSubsequence(vector<int> &nums, int target) {
vector<int> f(target + 1, INT_MIN);
f[0] = 0;
int s = 0;
for (int x : nums) {
s = min(s + x, target);
for (int j = s; j >= x; j--) {
f[j] = max(f[j], f[j - x] + 1);
}
}
return f[target] > 0 ? f[target] : -1;
}
};
java 解法, 执行用时: 18 ms, 内存消耗: 42 MB, 提交时间: 2023-10-29 10:41:36
class Solution {
public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
int[] f = new int[target + 1];
Arrays.fill(f, Integer.MIN_VALUE);
f[0] = 0;
int s = 0;
for (int x : nums) {
s = Math.min(s + x, target);
for (int j = s; j >= x; j--) {
f[j] = Math.max(f[j], f[j - x] + 1);
}
}
return f[target] > 0 ? f[target] : -1;
}
}
python3 解法, 执行用时: 1164 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-29 10:41:26
class Solution:
# 恰好装满型0-1背包
def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
f = [0] + [-inf] * target
s = 0
for x in nums:
s = min(s + x, target)
for j in range(s, x - 1, -1):
# f[j] = max(f[j], f[j - x] + 1)
# 手写 max 效率更高
if f[j] < f[j - x] + 1:
f[j] = f[j - x] + 1
return f[-1] if f[-1] > 0 else -1