-
Notifications
You must be signed in to change notification settings - Fork 0
LC 1218 [M] Longest Arithmetic Subsequence of Given Difference
Code with Senpai edited this page Jan 26, 2022
·
1 revision
dp[i] = 1 + dp[i-k]
class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
n = len(arr)
dp = {}
ans = 0
for num in arr:
target = num - difference
if target not in dp:
dp[num] = 1
else:
dp[num] = 1 + dp[target]
ans = max(ans, dp[num])
return ans
footer