LeetCode 2915: Length of the Longest Subsequence That Sums to Target

Explanation:

To solve this problem, we can use dynamic programming. We will maintain a HashMap to store the sum as the key and the length of the subsequence that sums up to that value as the value. We iterate through the given nums array and update the HashMap accordingly. At each index, we check if the current element combined with any of the previous subsequences can form the target sum. If so, we update the length of the subsequence that sums up to that value. Finally, we return the maximum length of the subsequence that sums up to the target.

• Algorithmic Idea:

  1. Create a HashMap to store the sum as the key and the length of the subsequence as the value.
  2. Iterate through the nums array and update the HashMap.
  3. At each index, check if the current element combined with any previous subsequences forms the target sum.
  4. Update the length of the subsequence if a valid combination is found.
  5. Return the maximum length of the subsequence that sums up to the target.

• Time Complexity: O(n), where n is the length of the nums array.

• Space Complexity: O(n) due to the HashMap.

:

class Solution {
    public int longestSubsequence(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        int maxLength = -1;
        
        for (int num : nums) {
            Map<Integer, Integer> newMap = new HashMap<>(map);
            for (int sum : map.keySet()) {
                int newSum = sum + num;
                if (newSum == target) {
                    maxLength = Math.max(maxLength, map.get(sum) + 1);
                }
                newMap.put(newSum, Math.max(newMap.getOrDefault(newSum, 0), map.get(sum) + 1));
            }
            map = newMap;
        }
        
        return maxLength;
    }
}