Skip to content

2915. Length of the Longest Subsequence That Sums to Target

SourceBiweekly Contest 116 Q3DifficultyMediumRating1658

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 <= 1000
  • 1 <= nums[i] <= 1000
  • 1 <= target <= 1000

Solutions

Solution 1: Dynamic Programming

Thinking

The longest subsequence whose sum is exactly \(target\) is a 0-1 knapsack (\(n,target \le 1000\)). Let \(f[i][j]\) be the best length using the first \(i\) numbers to make \(j\), with unreachable states at \(-\infty\).

The recurrence takes the better of skipping \(x\) and taking it. If \(f[n][target]\) is non-positive, no solution exists.

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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: Optimized Dynamic Programming

Thinking

Method 1’s \(f[i][j]\) depends only on the previous row, so the first index drops. Each number is used at most once, therefore the inner loop walks capacities downward. Space becomes \(O(target)\) with the same answer.

\(f[i][j]\) depends only on the previous row \(f[i-1][\cdot]\), so the first dimension can be dropped. Each number is used at most once, so \(j\) is updated from large to small. The space complexity becomes \(O(target)\).

1
2
3
4
5
6
7
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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];
}

Comments