2915. Length of the Longest Subsequence That Sums to Target

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.

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        vector<long long> dp(target + 1, INT_MIN);
        dp[0] = 0;
        for(auto n : nums) {
            for(int j = target - n; j >= 0; j--) {
                dp[j+n] = max(dp[j+n], dp[j] + 1);
            }
        }
        if(dp[target] > 0) return dp[target];
        return -1;
    }
};