Python에서 일정한 차이로 가장 긴 산술 부분 수열의 길이를 찾는 프로그램

<시간/>

숫자 nums의 목록과 다른 값 diff가 있다고 가정하면 하위 시퀀스의 연속 숫자 간의 차이가 diff와 동일한 가장 긴 산술 하위 시퀀스의 길이를 찾아야 합니다.

따라서 입력이 nums =[-1, 1, 4, 7, 2, 10] diff =3과 같으면 출력은 4가 됩니다. 왜냐하면 [1, 4, 7, 10]과 같은 부분 시퀀스를 선택할 수 있기 때문입니다. ].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

seen :=빈 사전, 키가 없을 때 기본값은 0입니다.
mx :=0
숫자 단위의 각 x에 대해 다음을 수행합니다.
- 만약 x - diff가 표시되면
  - 본[x] :=본[x - 차이] + 1
- 그렇지 않으면
  - 본[x] :=1
- mx :=최대 mx 및 본[x]
mx 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from collections import defaultdict
def solve(nums, diff):
   seen = defaultdict(int)
   mx = 0
   for x in nums:
      if x - diff in seen:
         seen[x] = seen[x - diff] + 1
      else:
         seen[x] = 1
      mx = max(mx, seen[x])
   return mx

nums = [-1, 1, 4, 7, 2, 10]
diff = 3
print(solve(nums, diff))

입력

[-1, 1, 4, 7, 2, 10], 3