和为目标值的最长子序列的长度
难度:
标签:
题目描述
You are given a 0-indexed array of integers nums, and an integer target.
Return the length of the longest subsequence of nums that sums up to target. If no such subsequence exists, return -1.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [1,2,3,4,5], target = 9 Output: 3 Explanation: There are 3 subsequences with a sum equal to 9: [4,5], [1,3,5], and [2,3,4]. The longest subsequences are [1,3,5], and [2,3,4]. Hence, the answer is 3.
Example 2:
Input: nums = [4,1,3,2,1,5], target = 7 Output: 4 Explanation: There are 5 subsequences with a sum equal to 7: [4,3], [4,1,2], [4,2,1], [1,1,5], and [1,3,2,1]. The longest subsequence is [1,3,2,1]. Hence, the answer is 4.
Example 3:
Input: nums = [1,1,5,4,5], target = 3 Output: -1 Explanation: It can be shown that nums has no subsequence that sums up to 3.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 10001 <= target <= 1000
代码结果
运行时间: 736 ms, 内存: 16.1 MB
import java.util.*;
import java.util.stream.Collectors;
/**
* 思路：
* 1. 使用回溯算法来找到所有和为target的子序列。
* 2. 使用Stream API来处理和找到最长的子序列。
*/
public class SolutionStream {
public int maxLengthSubsequence(int[] nums, int target) {
List<List<Integer>> subsequences = new ArrayList<>();
backtrack(nums, target, 0, 0, new ArrayList<>(), subsequences);
return subsequences.stream()
.filter(list -> list.stream().mapToInt(Integer::intValue).sum() == target)
.mapToInt(List::size)
.max()
.orElse(-1);
}
private void backtrack(int[] nums, int target, int start, int currentSum, List<Integer> currentList, List<List<Integer>> subsequences) {
if (currentSum == target) {
subsequences.add(new ArrayList<>(currentList));
return;
}
for (int i = start; i < nums.length; i++) {
if (currentSum + nums[i] <= target) {
currentList.add(nums[i]);
backtrack(nums, target, i + 1, currentSum + nums[i], currentList, subsequences);
currentList.remove(currentList.size() - 1);
}
}
}
public static void main(String[] args) {
SolutionStream sol = new SolutionStream();
int[] nums1 = {1, 2, 3, 4, 5};
int target1 = 9;
System.out.println(sol.maxLengthSubsequence(nums1, target1)); // 输出：3
int[] nums2 = {4, 1, 3, 2, 1, 5};
int target2 = 7;
System.out.println(sol.maxLengthSubsequence(nums2, target2)); // 输出：4
int[] nums3 = {1, 1, 5, 4, 5};
int target3 = 3;
System.out.println(sol.maxLengthSubsequence(nums3, target3)); // 输出：-1
}
}解释
方法:
该题解采用了动态规划的思路来解决问题。首先定义一个一维数组 f，其中 f[j] 表示达到和为 j 的子序列的最大长度。遍历数组 nums 中的每个数 num，然后逆向更新数组 f。对于每个 num，逆向更新从 target 到 num 的值，以防止同一个元素被重复使用。这种方式确保了每次更新都是基于之前状态的最优解。最后，如果 f[target] 是正数，则表示存在和为 target 的子序列，返回其长度；否则，返回 -1 表示不存在这样的子序列。
时间复杂度:
O(n*target)
空间复杂度:
O(target)
代码细节讲解
🦆
为什么在动态规划数组f的初始化中，除了f[0]被初始化为0外，其他的都初始化为非常小的负数（-n-1）？
▷🦆
在动态规划中为什么要逆序更新数组f，直接顺序更新有什么潜在的问题？
▷🦆
在代码中，变量s用于优化遍历的边界，具体是如何起到优化作用的？
▷🦆
如果nums数组中包含负数或零，这种动态规划方法是否仍然有效？如果无效，需要如何修改策略？
▷