Welcome to Subscribe On Youtube
2915. Length of the Longest Subsequence That Sums to Target
Description
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
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ as the length of the longest subsequence that selects several numbers from the first $i$ numbers and the sum of these numbers is exactly $j$. Initially, $f[0][0]=0$, and all other positions are $-\infty$.
For $f[i][j]$, we consider the $i$th number $x$. If we do not select $x$, then $f[i][j]=f[i-1][j]$. If we select $x$, then $f[i][j]=f[i-1][j-x]+1$, where $j\ge x$. Therefore, we have the state transition equation:
\[f[i][j]=\max\{f[i-1][j],f[i-1][j-x]+1\}\]The final answer is $f[n][target]$. If $f[n][target]\le0$, there is no subsequence with a sum of $target$, return $-1$.
The time complexity is $O(n\times target)$, and the space complexity is $O(n\times target)$. Here, $n$ is the length of the array, and $target$ is the target value.
We notice that the state of $f[i][j]$ is only related to $f[i-1][\cdot]$, so we can optimize the first dimension and reduce the space complexity to $O(target)$.
Solution 2
This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.
-
class Solution { public int lengthOfLongestSubsequence(List<Integer> nums, int target) { int n = nums.size(); int[][] f = new int[n + 1][target + 1]; final int inf = 1 << 30; for (int[] g : f) { Arrays.fill(g, -inf); } f[0][0] = 0; for (int i = 1; i <= n; ++i) { int x = nums.get(i - 1); for (int j = 0; j <= target; ++j) { f[i][j] = f[i - 1][j]; if (j >= x) { f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + 1); } } } return f[n][target] <= 0 ? -1 : f[n][target]; } } // Solution 2 class Solution { public int lengthOfLongestSubsequence(List<Integer> nums, int target) { int[] f = new int[target + 1]; final int inf = 1 << 30; Arrays.fill(f, -inf); f[0] = 0; for (int x : nums) { for (int j = target; j >= x; --j) { f[j] = Math.max(f[j], f[j - x] + 1); } } return f[target] <= 0 ? -1 : f[target]; } } -
class Solution { public: int lengthOfLongestSubsequence(vector<int>& nums, int target) { int n = nums.size(); int f[n + 1][target + 1]; memset(f, -0x3f, sizeof(f)); f[0][0] = 0; for (int i = 1; i <= n; ++i) { int x = nums[i - 1]; for (int j = 0; j <= target; ++j) { f[i][j] = f[i - 1][j]; if (j >= x) { f[i][j] = max(f[i][j], f[i - 1][j - x] + 1); } } } return f[n][target] <= 0 ? -1 : f[n][target]; } }; // Solution 2 class Solution { public: int lengthOfLongestSubsequence(vector<int>& nums, int target) { int f[target + 1]; memset(f, -0x3f, sizeof(f)); f[0] = 0; for (int x : nums) { for (int j = target; j >= x; --j) { f[j] = max(f[j], f[j - x] + 1); } } return f[target] <= 0 ? -1 : f[target]; } }; -
class Solution: def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int: n = len(nums) f = [[-inf] * (target + 1) for _ in range(n + 1)] f[0][0] = 0 for i, x in enumerate(nums, 1): for j in range(target + 1): f[i][j] = f[i - 1][j] if j >= x: f[i][j] = max(f[i][j], f[i - 1][j - x] + 1) return -1 if f[n][target] <= 0 else f[n][target] # Solution 2 class Solution: def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int: f = [0] + [-inf] * target for x in nums: for j in range(target, x - 1, -1): f[j] = max(f[j], f[j - x] + 1) return -1 if f[-1] <= 0 else f[-1] -
func lengthOfLongestSubsequence(nums []int, target int) int { n := len(nums) f := make([][]int, n+1) for i := range f { f[i] = make([]int, target+1) for j := range f[i] { f[i][j] = -(1 << 30) } } f[0][0] = 0 for i := 1; i <= n; i++ { x := nums[i-1] for j := 0; j <= target; j++ { f[i][j] = f[i-1][j] if j >= x { f[i][j] = max(f[i][j], f[i-1][j-x]+1) } } } if f[n][target] <= 0 { return -1 } return f[n][target] } // Solution 2 func lengthOfLongestSubsequence(nums []int, target int) int { f := make([]int, target+1) for i := range f { f[i] = -(1 << 30) } f[0] = 0 for _, x := range nums { for j := target; j >= x; j-- { f[j] = max(f[j], f[j-x]+1) } } if f[target] <= 0 { return -1 } return f[target] } -
function lengthOfLongestSubsequence(nums: number[], target: number): number { const n = nums.length; const f: number[][] = Array.from({ length: n + 1 }, () => Array(target + 1).fill(-Infinity)); f[0][0] = 0; for (let i = 1; i <= n; ++i) { const x = nums[i - 1]; for (let j = 0; j <= target; ++j) { f[i][j] = f[i - 1][j]; if (j >= x) { f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + 1); } } } return f[n][target] <= 0 ? -1 : f[n][target]; } // Solution 2 function lengthOfLongestSubsequence(nums: number[], target: number): number { const f: number[] = Array(target + 1).fill(-Infinity); f[0] = 0; for (const x of nums) { for (let j = target; j >= x; --j) { f[j] = Math.max(f[j], f[j - x] + 1); } } return f[target] <= 0 ? -1 : f[target]; }