k संख्याओं को हटाने के बाद आसन्न मानों का अधिकतम अंतर ज्ञात करने का पायथन प्रोग्राम

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

उदाहरण के लिए, यदि इनपुट nums = [15, 20, 30, 400, 1500] k = 2 है, तो आउटपुट 10 होगा, क्योंकि यदि हम [400, 1500] को हटा दें तो 20 और 30 का अंतर प्राप्त होता है।

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

abs_diff := nums में हर लगातार तत्वों के अंतर की सूची
एक फ़ंक्शन dp() परिभाषित करें। यह i, j, cnt लेगा
यदि cnt 0 के समान है, तो
- m := 0
- k को i से j तक के लिए, करें
  - m := m और abs_diff[k] में से अधिकतम
- m लौटाएं
dp(i + 1, j, cnt - 1) और dp(i, j - 1, cnt - 1) में से न्यूनतम लौटाएं
मुख्य विधि से निम्न करें:
dp(0, abs_diff का आकार - 1, k) लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, nums, k):
        abs_diff = [nums[i] - nums[i - 1] for i in range(1, len(nums))]
        def dp(i, j, cnt):
            if cnt == 0:
                m = 0
                for k in range(i, j + 1):
                    m = max(m, abs_diff[k])
                return m
            return min(dp(i + 1, j, cnt - 1), dp(i, j - 1, cnt - 1))
        return dp(0, len(abs_diff) - 1, k)

ob = Solution()
nums = [15, 20, 30, 400, 1500]
k = 2
print(ob.solve(nums, k))

इनपुट

[15, 20, 30, 400, 1500], 2