We’re asked to find the longest subsequence of numbers that all have a difference of difference from left to right.
We solve this using dynamic programming, but not with a memoization table like usual. Instead, we maintain dictionary of numbers seen, because, for a subsequence, we’re going to have to look backwards an arbitrary number of spaces.
The dictionary contains, for a given number, num, the length of the subsequence prior to reaching that number wherein all numbers have a difference of difference. So for example, if we’re looking at 2 and the difference is 2, we the compliment would be 4. If we’ve seen 4 before, it will return from a dictionary lookup, and then we append 1 to the subsequence and store dp[2]. Otherwise, the subsequence for dp[2] will be 1.
Across this process, we maximize the answer for the highest length subsequence we’ve seen so far.
The solution is as follows:
from collections import defaultdict
class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
dp = defaultdict(int)
ans = 1
for num in arr:
dp[num] = dp[num - difference] + 1
ans = max(ans, dp[num])
return ans_ Time Complexity:
O(n) - Where n is the length of arr, we iterate through the number list once.
_ Space Complexity:
O(n) - We maintain a memoization dictionary of size n.