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

<시간/>

nums라는 숫자 목록이 있다고 가정하고 두 개의 연속 숫자 사이의 차이가 양수와 음수를 번갈아 가며 나타나는 가장 긴 부분 수열의 크기를 찾아야 합니다. 그리고 첫 번째 차이는 양수일 수도 있고 음수일 수도 있습니다.

따라서 입력이 nums =[6, 10, 4, 2, 3, 9, 4, 7]과 같으면 출력은 6이 됩니다. 가능한 필수 하위 시퀀스는 [6, 10, 2, 9, 4입니다. , 7] 및 차이점은 [4, -8, 7, -5, 3]입니다.

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

n :=숫자 크기
dp :=크기가 2n이고 1로 채워진 목록
ans :=0
0에서 n 사이의 i에 대해
- 0~i 범위의 j에 대해
  - nums[j]
  - dp[i, 0] =최대 dp[i, 0] 및 (dp[j, 1] + 1)
- 그렇지 않으면 nums[j]> nums[i]일 때, then
  - dp[i, 1] =최대 dp[i, 1] 및 (dp[j, 0] + 1)
ans =최대 ans, dp[i, 0] 및 dp[i, 1])

반환

예제(파이썬)

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

class Solution:
   def solve(self, nums):
      n = len(nums)
      dp = [[1] * 2 for _ in range(n)]
      ans = 0
      for i in range(n):
         for j in range(i):
            if nums[j] < nums[i]:
               dp[i][0] = max(dp[i][0], dp[j][1] + 1)
            elif nums[j] > nums[i]:
               dp[i][1] = max(dp[i][1], dp[j][0] + 1)
         ans = max(ans, dp[i][0], dp[i][1])
      return ans
ob = Solution()
nums = [6, 10, 4, 2, 3, 9, 4, 7]
print(ob.solve(nums))

입력

[6, 10, 4, 2, 3, 9, 4, 7]