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.
1def longestSubsequence(arr, difference):
2 dp = {}
3 max_length = 0
4 for num in arr:
5 dp[num] = dp.get(num - difference, 0) + 1
6 max_length = max(max_length, dp[num])
7 return max_lengthThis Python solution uses a dictionary called dp where each key is a number from the array, and the value is the longest subsequence length ending with that number. We update the dictionary by iterating through each number in arr and deciding whether we can append the current number to an existing subsequence with the specified difference.
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).
#include <algorithm>
using namespace std;
int longestSubsequence(vector<int>& arr, int difference) {
int dp[20001] = {0};
int max_length = 0;
int offset = 10000;
for (int num : arr) {
int idx = num + offset;
int prev_idx = num - difference + offset;
dp[idx] = dp[prev_idx] + 1;
max_length = max(max_length, dp[idx]);
}
return max_length;
}This C++ solution aligns the array dp based on the constraint bounds, using simple array indexing to keep track of subsequences, which improves performance over hashmap lookups.