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

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

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

एल्गोरिदम (ब्रूट-फोर्स DFS)

• 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) कॉल करें
• मुख्य विधि से प्रत्येक 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