ধরুন, nums নামক একটি সংখ্যার তালিকা এবং অন্য একটি মান k দেওয়া আছে। আমাদের কাজ হল কমপক্ষে k সংখ্যক বিষম উপাদান সन्नিবেশকারী দীর্ঘতম ক্রমবর্ধমান উপক্রমের আকার বের করা।
উদাহরণস্বরূপ, nums = [12, 14, 16, 5, 7, 8] এবং k = 2 হলে আউটপুট হবে ৩, কারণ কমপক্ষে ২টি বিষম মান ধারণকারী দীর্ঘতম ক্রমবর্ধমান উপক্রম হল [5, 7, 8]।
সমাধানের ধাপসমূহ
- best := 0
- dp() ফাংশন সংজ্ঞায়িত করুন যা i, j, odd, taken প্যারামিটার নেয়
- যদি odd >= k হয়, তবে best := max(best, taken)
- যদি j == len(nums) হয়, তবে ফেরত যান
- যদি nums[j] > nums[i] হয়, তবে dp(j, j+1, odd + (nums[j] & 1), taken + 1) কল করুন
- dp(i, j+1, odd, taken) কল করুন
- মূল ফাংশন থেকে 0 থেকে len(nums)-1 পর্যন্ত i এর জন্য dp(i, i+1, nums[i] & 1, 1) কল করুন
- best ফেরত দিন
উদাহরণ কোড
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
