深圳企业网站seo,抖音搜索推广首选帝搜软件平台,wordpress优酷无广告,做视频网站推广挣钱吗给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
返回和为 target 的 nums 子序列中#xff0c;子序列 长度的最大值 。如果不存在和为 target 的子序列#xff0c;返回 -1 。
子序列 指的是从原数组中删除一些或者不删除任何元素后#xff0c;剩余元素保持原…给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
返回和为 target 的 nums 子序列中子序列 长度的最大值 。如果不存在和为 target 的子序列返回 -1 。
子序列 指的是从原数组中删除一些或者不删除任何元素后剩余元素保持原来的顺序构成的数组。 复杂度O(N)。 思路0-1背包问题。
class Solution {public int lengthOfLongestSubsequence(ListInteger nums, int target) {// 0-1背包问题/**背包容量为target物品体积为nums.get(i)物品价值均为1物品有放入与不放入两种选择dp[i] max(dp[i], dp[i-x]1) */int n nums.size();int s 0;// target为背包容量int[] dp new int[target1];Arrays.setAll(dp, e-Integer.MIN_VALUE);dp[0] 0;for(int i0; in; i) {// 当前物品体积int x nums.get(i);// 放入体积为s的物体s Math.min(sx, target);// 更新dp数组for(int js; jx; j--) {dp[j] Math.max(dp[j], dp[j-x]1);}}return dp[target]0?dp[target]:-1;}
}
