免费稳定的网站空间,谷歌官方建站服务,天河区营销型网站建设,营销网站定制公司给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。 返回和为 target 的 nums 子序列中#xff0c;子序列 长度的最大值 。如果不存在和为 target 的子序列#xff0c;返回 -1 。 子序列 指的是从原数组中删除一些或者不删除任何元素后#xff0c;剩余元素保持原来… 给你一个下标从 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 代码
#includeiostream
#includevectorusing namespace std;class Solution {public:int lengthOfLongestSubsequence(vectorint nums, int target) {int len nums.size(), i 0, j 0;vectorvectorint dp(len, vectorint(target1, 0));for(i 0; i nums.size(); i){for(j 0; j target; j){if(i 0){// 初始化if(j nums[i])dp[0][j] 1;}else{if(j nums[i] dp[i-1][j-nums[i]] ! 0){dp[i][j] max(dp[i-1][j], dp[i-1][j-nums[i]] 1);}else if(j nums[i]){dp[i][j] max(dp[i-1][j], 1);}elsedp[i][j] dp[i-1][j];}}}if(dp[len-1][target] 0) return -1;else return dp[len-1][target];}};int main(){Solution obj;vectorint nums({1,2,3,4,5});int res obj.lengthOfLongestSubsequence(nums, 9);cout res;return 0;
} 解题思路 1使用动态规划思想。 2首先创建一个 dp 数组。 3根据题目对 dp 进行初始化。题目主要有一个 target因此我们将对 满足第一个元素的大小进行初始化。 4根据题目找到递归表达式。本题有大于、等于和小于三种情况需要判断。
