1218. Longest Arithmetic Subsequence of Given Difference

1218. Longest Arithmetic Subsequence of Given Difference

 

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        # 주어진 배열 arr에서 
        # 차이가 difference인 '부분 수열(subsequence)'의 
        # 최대 길이를 찾는 것
        dp = [1] * len(arr)

        res = -float("inf")

        for i in range(len(arr)-1, -1, -1):
            for j in range(i+1, len(arr)):
                if arr[i] + difference == arr[j]:
                    dp[i] = max(dp[i], 1+dp[j])
            res = max(res, dp[i])

        return res

 

시간 복잡도 O(n^2) 로 인해, 시간 제한 걸림

=> 따라서, 해시맵을 사용해서, 이전 계산 결과를 저장(메모이제이션) 하는 방식으로

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        # 주어진 배열 arr에서 
        # 차이가 difference인 '부분 수열(subsequence)'의 
        # 최대 길이를 찾는 것

        """
        기본 로직, 그러나 시간 복잡도 O(n^2) 로 인해, 시간 제한
        dp = [1] * len(arr)

        res = -float("inf")

        for i in range(len(arr)-1, -1, -1):
            for j in range(i+1, len(arr)):
                if arr[i] + difference == arr[j]:
                    dp[i] = max(dp[i], 1+dp[j])
            res = max(res, dp[i])

        return res        
        """
        # 따라서, 해시맵을 사용해서, 이전 계산 결과를 저장(메모이제이션) 하는 방식으로/
        # dp[x]는 숫자 x로 끝나는 차이가 difference인 부분 수열의 최대 길이를 저장
        dp = {}

        for num in arr:
            # 이전 값 num - difference가 dp에 있으면, 해당 값을 이용해 dp[num] 갱신
            if num - difference in dp:
                dp[num] = dp[num - difference] + 1
            else:
                dp[num] = 1 # num만 포함하는 부분 수열의 길이는 1
        return max(dp.values())