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

Python에서 최소 k 개의 홀수 값으로 가장 길게 증가하는 부분 시퀀스의 길이를 찾는 프로그램

<시간/>

nums라고 하는 숫자 목록과 또 다른 값 k가 있다고 가정하면 최소 k개의 홀수 요소가 있는 가장 긴 증가 부분 수열의 크기를 찾아야 합니다.

따라서 입력이 nums =[12, 14, 16, 5, 7, 8] k =2와 같으면 출력은 3이 됩니다. 최소 2개의 홀수 값이 있는 가장 긴 증가 부분 시퀀스는 [5, 7, 8].

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

  • 최고 :=0

  • dp() 함수를 정의합니다. 이것은 i, j, 홀수, 취해질 것입니다

  • 홀수>=k이면

    • 최고 :=최고 및 채택의 최대값

  • j가 nums의 크기와 같으면

    • 반환

  • nums[j]> nums[i]이면

    • dp(j, j + 1, 홀수 +(nums[j] AND 1) , 취함 + 1)

  • dp(i, j + 1, 홀수, 취함)

  • 주요 방법에서 다음을 수행하십시오 -

  • 범위 0에서 숫자 크기까지의 i에 대해

    • dp(i, i + 1, nums[i] AND 1, 1)

  • 최고의 반환

예시

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

class Solution:
def solve(self, nums, k):
   best = 0
   def dp(i, j, odd, taken):
      nonlocal best
      if odd >= k:
         best = max(best, taken)
      if j == len(nums):
         return
      if nums[j] > nums[i]:
         dp(j, j + 1, odd + (nums[j] & 1), taken + 1)
      dp(i, j + 1, odd, taken)
   for i in range(len(nums)):
      dp(i, i + 1, nums[i] & 1, 1)
   return best
ob = Solution()
nums = [12, 14, 16, 5, 7, 8]
k = 2
print(ob.solve(nums, k))

입력

[12, 14, 16, 5, 7, 8], 2

출력

3