Skip to content

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

 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

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