JAVA | DP | 2 Lines |Easy
Intuition\n01 Knapsack problem\n\n# Approach\nInput: nums = [4,1,3,2,1,5], target = 7\nOutput: 4\n\n\nThe above solution can be done by using only one array\n\n
# Intuition\n01 Knapsack problem\n\n# Approach\nInput: nums = [4,1,3,2,1,5], target = 7\nOutput: 4\n![image.png](https://assets.leetcode.com/users/images/11cd0bc8-de94-4571-974f-a4a34b2e595b_1717837302.7041097.png)\n\nThe above solution can be done by using only one array\n\n# Complexity\n- Time complexity:\n- O(target*size(nums))\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\n    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {\n       int[] arr = new int[target+1];\n\n       for(int n: nums){\n        for(int i= target; i>0 && i>=n; i--) {\n            arr[i] = Math.max(arr[i], arr[i-n]>0?arr[i-n]+1:i==n?1:0);\n        }\n       }\n\n       return arr[target]==0?-1:arr[target];\n    }\n}\n```
['Java']