1027. Longest Arithmetic Subsequence

1027. Longest Arithmetic Subsequence

 

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        # longestArithSeq 는 같은 간격을 같는 LIS 를 찾는 거라서.
        # 즉, "등차수열을 이루는 가장 긴 부분 수열의 길이"
        # 해쉬맵에 lenLIS 와 간격 difference 를 저장해야 할듯
        dp = {} # 키: (index, difference) -> 값: 등차수열의 길이 

        max_len = 1 # 최소 길이는 1

        for i in range(len(nums)): # 정방향 순회
            for j in range(i): # i 이전 값들 순회
                diff = nums[i] - nums[j] # 차이 계산                
                
                # dp[j, diff]의 값이 없으면 기본값 1을 사용
                dp[i, diff] = dp.get((j, diff), 1) + 1 # 수열 길이 갱신
                max_len = max(max_len, dp[i, diff])  # 최대 길이 갱신

        return max_len