Length of the Longest Subsequence That Sums to Target

medium dp knapsack array

Problem

Given an array of positive integers nums and an integer target, return the length of the longest subsequence of nums that adds up to exactly target. A subsequence keeps the original order but may skip elements. If no subsequence sums to target, return -1.

Inputnums = [1, 2, 3, 4, 5], target = 9

Output3

Several subsequences sum to 9, e.g. {2, 3, 4} and {1, 3, 5}. The longest of them uses 3 elements, so the answer is 3.

nums (comma-separated)

target

def length_of_longest_subsequence(nums, target):
    NEG = float("-inf")
    dp = [NEG] * (target + 1)
    dp[0] = 0
    for x in nums:
        for s in range(target, x - 1, -1):
            if dp[s - x] != NEG:
                dp[s] = max(dp[s], dp[s - x] + 1)
    return dp[target] if dp[target] != NEG else -1

function lengthOfLongestSubsequence(nums, target) {
  const NEG = -Infinity;
  const dp = new Array(target + 1).fill(NEG);
  dp[0] = 0;
  for (const x of nums) {
    for (let s = target; s >= x; s--) {
      if (dp[s - x] !== NEG) {
        dp[s] = Math.max(dp[s], dp[s - x] + 1);
      }
    }
  }
  return dp[target] !== NEG ? dp[target] : -1;
}

class Solution {
    public int lengthOfLongestSubsequence(int[] nums, int target) {
        final int NEG = Integer.MIN_VALUE;
        int[] dp = new int[target + 1];
        Arrays.fill(dp, NEG);
        dp[0] = 0;
        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                if (dp[s - x] != NEG) {
                    dp[s] = Math.max(dp[s], dp[s - x] + 1);
                }
            }
        }
        return dp[target] != NEG ? dp[target] : -1;
    }
}

int lengthOfLongestSubsequence(vector<int>& nums, int target) {
    const int NEG = INT_MIN;
    vector<int> dp(target + 1, NEG);
    dp[0] = 0;
    for (int x : nums) {
        for (int s = target; s >= x; s--) {
            if (dp[s - x] != NEG) {
                dp[s] = max(dp[s], dp[s - x] + 1);
            }
        }
    }
    return dp[target] != NEG ? dp[target] : -1;
}

Explanation

This is a flavour of the 0/1 knapsack. The "capacity" is the target sum, each number can be used at most once, and instead of maximizing value we want to maximize how many numbers we pick while landing on exactly that sum.

We keep an array dp of length target + 1. The meaning is: dp[s] = the largest count of elements that form some subsequence summing to exactly s. A sum we cannot reach yet is marked with negative infinity so it never wins a max.

We start with dp[0] = 0: the empty subsequence sums to 0 using 0 elements. Every other entry starts unreachable.

For each number x we scan s from target down to x. If dp[s - x] is reachable, then by adding x we can reach s with one more element, so dp[s] = max(dp[s], dp[s - x] + 1). Walking downward guarantees each x is used at most once during this pass.

Example: nums = [1, 2, 3, 4, 5], target = 9. After processing every number, dp[9] holds 3, because the best subsequence summing to 9 (for instance {2, 3, 4}) uses three elements. If dp[target] were still negative infinity, no subsequence hits the target and we return -1.

Time: O(n · target) Space: O(target)