Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 주어진 목록의 가장 긴 산술 부분 시퀀스의 길이를 찾는 프로그램

<시간/>

nums라는 숫자 목록이 있다고 가정하고 가장 긴 산술 부분 수열의 길이를 찾아야 합니다. 시퀀스 S[i]는 S[i+1] - S[i]가 범위(0 ≤ i

따라서 입력이 nums =[1, 4, 7, 10, 13, 20, 16]과 같으면 출력은 6이 되고 하위 시퀀스 [1, 4, 7, 10, 13, 16]은 산술 연산입니다. 연속된 각 요소의 차이가 3이기 때문입니다.

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

  • n :=arr의 크기
  • n <=1이면
    • 반환 n
  • res :=0
  • dp :=빈 지도, 기본적으로 키를 찾을 수 없는 경우 1을 저장합니다.
  • 1 ~ n - 1 범위의 i에 대해
    • 0 ~ i - 1 범위의 j에 대해 수행
      • 차이 :=arr[i] - arr[j]
      • dp[i, diff] :=dp[j, diff] + 1
      • res :=res 및 dp[i, diff
        • 의 최대값
  • 반환 결과

예제(파이썬)

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

from collections import defaultdict
class Solution:
   def solve(self, arr):
      n = len(arr)
      if n <= 1:
         return n
      res = 0
      dp = defaultdict(lambda: 1)
      for i in range(1, n):
         for j in range(i):
            diff = arr[i] - arr[j]
            dp[i, diff] = dp[j, diff] + 1
            res = max(res, dp[i, diff])
      return res
ob = Solution()
nums = [1, 4, 7, 10, 13, 20, 16]
print(ob.solve(nums))

입력

[1, 4, 7, 10, 13, 20, 16]

출력

6