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