โปรแกรมหาความต่างสูงสุดของค่าที่อยู่ติดกันหลังจากลบ k ตัวเลขใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียงจากน้อยไปมาก เราต้องการลบ k ตัวเลขออกจากรายการ เพื่อให้ความต่างสูงสุดระหว่างค่าที่อยู่ติดกันมีค่าน้อยที่สุด แล้วคืนค่าความต่างนั้น

เช่น ถ้าอินพุตเป็น nums = [15, 20, 30, 400, 1500] k = 2 ผลลัพธ์จะเป็น 10 เนื่องจากลบ [400, 1500] จะได้ความต่างระหว่าง 20 และ 30

ขั้นตอนการแก้ปัญหา

• abs_diff := รายการความต่างของแต่ละคู่ที่อยู่ติดกันใน nums
• กำหนดฟังก์ชัน dp(i, j, cnt):
  • ถ้า cnt == 0 คืนค่าความต่างสูงสุดในช่วง i ถึง j
  • คืนค่า min(dp(i+1, j, cnt-1), dp(i, j-1, cnt-1))
• จากเมธอดหลัก เรียก dp(0, len(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