สมมติว่าเรามีรายการตัวเลขที่แสดงตำแหน่งของรถในช่วงเวลาที่เว้นระยะเท่ากัน เราต้องหาขนาดของรายการย่อยที่ยาวที่สุดที่รถแล่นด้วยความเร็วคงที่
ดังนั้น หากอินพุตเท่ากับตำแหน่ง =[0, 4, 8, 12, 6, 4, 0] ผลลัพธ์จะเป็น 4 เนื่องจากรายการย่อยคือ [0, 4, 8, 12]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- j :=1
- max_cnt :=0, ปัจจุบัน :=0
- ระยะทาง :=|ตำแหน่ง[0] - ตำแหน่ง[1]|
- ในขณะที่ j <ขนาดของตำแหน่ง ทำ
- ก่อนหน้า :=ตำแหน่ง[j - 1]
- ถ้าระยะทางเท่ากับ |positions[j] - ก่อนหน้า| แล้ว
- ปัจจุบัน :=ปัจจุบัน + 1
- มิฉะนั้น
- max_cnt :=สูงสุดของ max_cnt และกระแส
- ปัจจุบัน :=1
- ระยะทาง :=|positions[j] - ก่อนหน้า|
- max_cnt :=สูงสุดของ max_cnt และกระแส
- j :=j + 1
- ส่งคืน max_cnt + 1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, positions): j = 1 max_cnt = 0 current = 0 distance = abs(positions[0] - positions[1]) while j < len(positions): prev = positions[j - 1] if distance == abs(positions[j] - prev): current += 1 else: max_cnt = max(max_cnt, current) current = 1 distance = abs(positions[j] - prev) max_cnt = max(max_cnt, current) j += 1 return max_cnt + 1 ob = Solution() positions = [0, 4, 8, 12, 6, 4, 0] print(ob.solve(positions))
อินพุต
[0, 4, 8, 12, 6, 4, 0]
ผลลัพธ์
4
