สมมุติว่ามีนักขี่มอเตอร์ไซค์กำลังเดินทาง มี n จุดที่แตกต่างกันในการเดินทางบนถนนของเขาที่ระดับความสูงต่างกัน นักขี่จักรยานเริ่มต้นการเดินทางจากจุดที่ 0 ด้วยระดับความสูง 0 หากเรามีลำดับที่เรียกว่า gain โดยมีองค์ประกอบ n ตัว gain[i] คืออัตราขยายสุทธิในระดับความสูงระหว่างจุด i กับ i + 1 สำหรับทุกคน (0 <=i
ดังนั้น หากอินพุตเป็นเหมือนค่าเกน =[-4,2,6,1,-6] ผลลัพธ์จะเป็น 5 เนื่องจากระดับความสูงคือ [0,-4,-2,4,5,-1] , ดังนั้นสูงสุดคือ 5.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สูงสุด :=0
-
run_alt :=0
-
สำหรับแต่ละเดลต้าในกำไร ทำ
-
run_alt :=run_alt + เดลต้า
-
สูงสุด :=สูงสุดของค่าสูงสุดและ run_alt
-
-
ผลตอบแทนสูงสุด
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(gain): maximum = 0 run_alt = 0 for delta in gain: run_alt += delta maximum = max(maximum, run_alt) return maximum gain = [-4,2,6,1,-6] print(solve(gain))
อินพุต
[-4,2,6,1,-6]
ผลลัพธ์
5