পাইথনে 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