สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และมีการเรียงลำดับจากน้อยไปมาก เราต้องลบค่า k ออกจากรายการ เพื่อให้ค่าความแตกต่างสูงสุดระหว่างค่าที่อยู่ติดกันสองค่ามีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ และในที่สุดก็พบความแตกต่าง
ดังนั้น หากอินพุตเท่ากับ nums =[15, 20, 30, 400, 1500] k =2 ผลลัพธ์จะเป็น 10 ราวกับว่าเราลบ [400, 1500] เพื่อให้ได้ผลต่าง 20 และ 30
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- abs_diff :=รายการความแตกต่างขององค์ประกอบที่ต่อเนื่องกันเป็น nums
- กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, j, cnt
- ถ้า cnt เหมือนกับ 0 แล้ว
- ม :=0
- สำหรับ k ในช่วง i ถึง j ทำ
- m :=สูงสุดของ m และ abs_diff[k]
- คืนสินค้า
- คืนค่าขั้นต่ำของ 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
