Similar Problems
Similar Problems not available
Longest Subsequence With Limited Sum - Leetcode Solution
Companies:
LeetCode: Longest Subsequence With Limited Sum Leetcode Solution
Difficulty: Easy
Topics: greedy binary-search array prefix-sum sorting
Problem Statement: Given an integer array nums, you need to find the longest subsequence that has a sum less than or equal to target. If there is no such subsequence, return 0.
Example 1: Input: nums = [10,2,-2,-20,10], target = -10 Output: 2 Explanation: The longest subsequence is [2,-2] as the sum is -10.
Example 2: Input: nums = [1,2,3,4,5], target = 11 Output: 5 Explanation: The entire array is the longest subsequence as the sum is less than or equal to target.
Approach: This is dynamic programming problem. We will use the memoization technique. We will try to find the longest subsequence that has a sum less than or equal to target for each index one by one. We will first create a 2D array dp with size (nums.length+1) x (target+1) and will initialize it with 0s. Here dp[i][j] represents the longest subsequence that has a sum less than or equal to j till index i-1 (0-based indexing).
We will start filling the dp array by iterating the nums array from 1st index to last. For each index i we will iterate all the values from 1 to target and fill the dp[i][j]. There are two cases:
-
We can ignore the current element: In this case the longest subsequence till index i will be same as the longest subsequence till index i-1. Hence, we just copy dp[i-1][j] to dp[i][j].
-
We can include the current element: In this case, we check if nums[i-1] <= j. If yes, then we check if including nums[i-1] will result in a longer subsequence than already we have. If yes, we update dp[i][j] with that length.
Finally, find the maximum length of subsequence computed from dp[][] array and return it.
Code:
public int longestSubsequence(int[] nums, int target) { int n = nums.length; int[][] dp = new int[n+1][target+1]; int res = 0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=target; j++) {
if(nums[i-1] <= j) {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i-1]]+1);
} else {
dp[i][j] = dp[i-1][j];
}
res = Math.max(dp[i][j], res);
}
}
return res;
}
Complexity Analysis:
Time Complexity: O(n*target). The nested loops iterate n and target elements each.
Space Complexity: O(ntarget). We use dp array of size ntarget.
Longest Subsequence With Limited Sum Solution Code
1