पायथन में कम से कम k विषम मूल्यों के साथ सबसे लंबे समय तक बढ़ते क्रम की लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k है, हमें कम से कम k विषम तत्वों के साथ सबसे लंबे समय तक बढ़ते क्रम का आकार खोजना होगा।

इसलिए, यदि इनपुट nums =[12, 14, 16, 5, 7, 8] k =2 की तरह है, तो आउटपुट 3 होगा, क्योंकि कम से कम 2 विषम मानों के साथ सबसे लंबे समय तक बढ़ने वाला क्रम [5, 7] है। 8].

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सर्वोत्तम:=0

• एक फ़ंक्शन को परिभाषित करें dp() । इसमें i, j, विषम, लिया जाएगा

• अगर विषम>=k, तो

  • श्रेष्ठ :=अधिकतम सर्वोत्तम और लिया गया

• यदि j अंकों के आकार के समान है, तो

  • वापसी

• अगर अंक [जे]> अंक [i], तो

  • dp(j, j + 1, विषम +(nums[j] और 1) , लिया गया + 1)

• dp(i, j + 1, विषम, लिया गया)

• मुख्य विधि से निम्न कार्य करें -

• मैं के लिए 0 से लेकर अंकों के आकार तक, करें

  • dp(i, i + 1, nums[i] और 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