LC-2915 Medium LeetCode

2915. Length of the Longest Subsequence That Sums to Target

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 37% Topics: Array, Dynamic Programming

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n * t)
# Space: O(t)

# knapsack dp
class Solution(object):
    def lengthOfLongestSubsequence(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [-1]*(target+1)
        dp[0] = 0
        for x in nums:
            for i in reversed(xrange(x, len(dp))):
                if dp[i-x] != -1:
                    dp[i] = max(dp[i], dp[i-x]+1)
        return dp[-1]

Solution from kamyu104/LeetCode-Solutions · MIT