मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और उन्हें आरोही क्रम में क्रमबद्ध किया जाता है, हमें सूची से k मानों को हटाना होगा ताकि किन्हीं दो आसन्न मानों के बीच अधिकतम अंतर यथासंभव न्यूनतम हो, और अंत में अंतर ज्ञात करें। पी>
इसलिए, यदि इनपुट संख्या =[15, 20, 30, 400, 1500] k =2 की तरह है, तो आउटपुट 10 होगा, जैसे कि हम 20 और 30 का अंतर पाने के लिए [400, 1500] हटाते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- abs_diff :=अंकों में लगातार प्रत्येक तत्वों के अंतर की एक सूची
- एक फ़ंक्शन को परिभाषित करें dp() । इसमें i, j, cnt . लगेगा
- यदि cnt 0 के समान है, तो
- एम :=0
- k के लिए i से j तक, do
- m :=अधिकतम m और abs_diff[k]
- वापसी मी
- dp(i + 1, j, cnt-1) और dp(i, j-1, cnt-1) का न्यूनतम रिटर्न करें
- मुख्य विधि से निम्न कार्य करें:
- रिटर्न dp(0, size of 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
आउटपुट
10