ধরুন আমাদের কাছে সংখ্যা বলা সংখ্যার একটি তালিকা আছে এবং সেগুলিকে ক্রমবর্ধমান ক্রমে সাজানো হয়েছে, আমাদের তালিকা থেকে k মানগুলি মুছে ফেলতে হবে যাতে যেকোনো দুটি সন্নিহিত মানের মধ্যে সর্বাধিক পার্থক্য যতটা সম্ভব সর্বনিম্ন হয় এবং অবশেষে পার্থক্যটি খুঁজে বের করতে পারি। পি>
সুতরাং, ইনপুট যদি nums =[15, 20, 30, 400, 1500] k =2 এর মত হয়, তাহলে আউটপুট হবে 10, যেমন আমরা 20 এবং 30 এর পার্থক্য পেতে [400, 1500] সরিয়ে ফেলি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- abs_diff :=সংখ্যায় প্রতিটি ধারাবাহিক উপাদানের পার্থক্যের একটি তালিকা
- একটি ফাংশন dp() সংজ্ঞায়িত করুন। এর জন্য i, j, cnt লাগবে
- যদি cnt 0 এর মত হয়, তাহলে
- m :=0 i থেকে j রেঞ্জের মধ্যে k-এর জন্য
- করুন
- 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
আউটপুট
10
