Sponsored
Sponsored
This approach uses a hash map (or dictionary) to keep track of the longest subsequence length that can be achieved ending with a specific value. For each element in the array, we check if there is an arithmetic subsequence ending with the element minus the given difference. If such a subsequence exists, we calculate the current subsequence length. Otherwise, we start a new subsequence from this element.
Time Complexity: O(n), where n is the length of arr. We iterate over the array once.
Space Complexity: O(n), where n is the number of distinct elements in arr stored in the dictionary.
1function longestSubsequence(arr, difference) {
2 const dp = new Map();
3 let max_length = 0;
4 for (const num of arr) {
5 dp.set(num, (dp.get(num - difference) || 0) + 1);
6 max_length = Math.max(max_length, dp.get(num));
7 }
8 return max_length;
9}This JavaScript implementation uses a Map object to keep track of subsequence lengths. We iterate over the numbers, updating the map based on whether the preceding number minus the difference has been seen.
This approach utilizes an array to store information about each possible element value scaled according to the constraints. For each element in arr, determine if there is a previous subsequence that can be extended using direct array access.
Time Complexity: O(n), where n is the length of arr.
Space Complexity: O(1) (constant size array mentioned in constraints).
This Python solution uses an indexed array to store the length of subsequences directly aligned by the values of elements. We handle negative indices by offsetting the array from the minimal possible value.