✅☑[C++/Java/Python/JavaScript] || DP || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n1. The function calculates the length of the longest subsequence with a targe
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n1. The function calculates the length of the longest subsequence with a target sum for a given array `nums`.\n\n1. It uses a 2D dynamic programming table `dp`, where `dp[i][j]` represents the length of the longest subsequence in the first `i` elements of the nums array that sums up to `j`.\n\n1. Initially, it sets `dp[i][0]` to 0 for all `i` because the longest subsequence with a target sum of 0 is always empty.\n\n1. It iterates through the elements in `nums` and the target sums, filling in the `dp` table accordingly.\n\n1. If the current element can contribute to the current sum, it updates `dp[i][j]` with the maximum of two values:\n\n    - The result without including the current element (`dp[i-1][j]`).\n    - The result when considering the current element (`1 + dp[i-1][j-nums[i-1]]`), adding 1 to the length of the subsequence.\n1. Finally, it returns `dp[n][sum]`, where n is the length of the `nums` array, representing the length of the longest subsequence with the target sum.\n\n\n\n# Complexity\n- *Time complexity:*\n   $$O(n*sum)$$\n    \n\n- *Space complexity:*\n   $$O(n*sum)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int lengthOfLongestSubsequence(vector<int>& nums, int sum) {\n        int n = nums.size();\n        // Create a 2D array to store the dynamic programming results.\n        vector<vector<int>> dp(n + 1, vector<int>(sum + 1, -1));\n\n        for (int i = 0; i < n + 1; i++)\n            dp[i][0] = 0; // Longest subsequence when the target sum is 0.\n\n        for (int i = 1; i < n + 1; i++) {\n            for (int j = 1; j < sum + 1; j++) {\n                // Initially, set the result to be the same as the result for the previous element.\n                dp[i][j] = dp[i - 1][j];\n\n                // Check if the current element can contribute to the current sum.\n                if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]] != -1)\n                    dp[i][j] = max(1 + dp[i - 1][j - nums[i - 1]], dp[i][j]);\n            }\n        }\n\n        return dp[n][sum]; // Return the result for the entire array with the target sum.\n    }\n};\n\n\n```\n\n```C []\n\n#include <stdio.h>\n\nint max(int a, int b) {\n    return (a > b) ? a : b;\n}\n\nint lengthOfLongestSubsequence(int *nums, int n, int sum) {\n    // Create a 2D array to store the dynamic programming results.\n    int dp[n + 1][sum + 1];\n\n    for (int i = 0; i <= n; i++)\n        dp[i][0] = 0; // Longest subsequence when the target sum is 0.\n\n    for (int i = 1; i <= n; i++) {\n        for (int j = 1; j <= sum; j++) {\n            // Initially, set the result to be the same as the result for the previous element.\n            dp[i][j] = dp[i - 1][j];\n\n            // Check if the current element can contribute to the current sum.\n            if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]] != -1)\n                dp[i][j] = max(1 + dp[i - 1][j - nums[i - 1]], dp[i][j]);\n        }\n    }\n\n    return dp[n][sum]; // Return the result for the entire array with the target sum.\n}\n\nint main() {\n    int nums[] = {1, 2, 3, 4, 5};\n    int n = sizeof(nums) / sizeof(nums[0]);\n    int sum = 9;\n\n    int result = lengthOfLongestSubsequence(nums, n, sum);\n    printf("Length of the longest subsequence: %d\\n", result);\n\n    return 0;\n}\n\n\n\n```\n```Java []\n\nclass Solution {\n    public int lengthOfLongestSubsequence(int[] nums, int sum) {\n        int n = nums.length;\n        int[][] dp = new int[n + 1][sum + 1];\n        \n        for (int i = 0; i < n + 1; i++)\n            dp[i][0] = 0;\n\n        for (int i = 1; i < n + 1; i++) {\n            for (int j = 1; j < sum + 1; j++) {\n                dp[i][j] = dp[i - 1][j];\n\n                if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]] != -1)\n                    dp[i][j] = Math.max(1 + dp[i - 1][j - nums[i - 1]], dp[i][j]);\n            }\n        }\n\n        return dp[n][sum];\n    }\n}\n\n\n```\n```python3 []\n\nclass Solution:\n    def lengthOfLongestSubsequence(self, nums, sum):\n        n = len(nums)\n        dp = [[-1] * (sum + 1) for _ in range(n + 1)]\n        \n        for i in range(n + 1):\n            dp[i][0] = 0\n        \n        for i in range(1, n + 1):\n            for j in range(1, sum + 1):\n                dp[i][j] = dp[i - 1][j]\n                if j >= nums[i - 1] and dp[i - 1][j - nums[i - 1]] != -1:\n                    dp[i][j] = max(1 + dp[i - 1][j - nums[i - 1]], dp[i][j])\n        \n        return dp[n][sum]\n\n\n```\n```javascript []\nclass Solution {\n    lengthOfLongestSubsequence(nums, sum) {\n        const n = nums.length;\n        const dp = new Array(n + 1);\n        for (let i = 0; i <= n; i++) {\n            dp[i] = new Array(sum + 1).fill(-1);\n        }\n\n        for (let i = 0; i <= n; i++) {\n            dp[i][0] = 0;\n        }\n\n        for (let i = 1; i <= n; i++) {\n            for (let j = 1; j <= sum; j++) {\n                dp[i][j] = dp[i - 1][j];\n\n                if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]] !== -1) {\n                    dp[i][j] = Math.max(1 + dp[i - 1][j - nums[i - 1]], dp[i][j]);\n                }\n            }\n        }\n\n        return dp[n][sum];\n    }\n}\n\n```\n\n\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Dynamic Programming', 'C', 'C++', 'Java', 'Python3', 'JavaScript']