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

Master LeetCode problem 2915 (Length of the Longest Subsequence That Sums to Target), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2915. Length of the Longest Subsequence That Sums to Target

Medium

Array Dynamic Programming

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2915 (Length of the Longest Subsequence That Sums to Target)?

This page provides optimized solutions for LeetCode problem 2915 (Length of the Longest Subsequence That Sums to Target) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2915 (Length of the Longest Subsequence That Sums to Target)?

The time complexity for LeetCode 2915 (Length of the Longest Subsequence That Sums to Target) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2915 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2915 in Java, C++, or Python.

Back to LeetCode Solutions