2915：和为目标值的最长子序列的长度（1658 分）

力扣第 116 场双周赛第 3 题

题目

给你一个下标从 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 <= 1000
• 1 <= nums[i] <= 1000
• 1 <= target <= 1000

相似问题：

• 0322：零钱兑换
• 0518：零钱兑换 II
• 3201：找出有效子序列的最大长度 I（1663 分）
• 3202：找出有效子序列的最大长度 II（1973 分）

分析

按选不选最后一个元素即可递推。可以将 dp 数组优化为一维。

解答

1
2
3
4
5
6
7
8

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [0]+[-inf]*target
        for x in nums:
            for j in range(target,x-1,-1):
                f[j] = max(f[j],1+f[j-x])
        return max(-1,f[-1])

2092 ms