Chương trình tìm độ cao cao nhất của một điểm trong Python

Giả sử có một người đạp xe đi chuyến đường dài. Có n điểm khác nhau ở các độ cao khác nhau. Người đạp xe bắt đầu từ điểm 0 với độ cao 0. Nếu ta có dãy gain với n phần tử, gain[i] là tăng giảm độ cao giữa điểm i và i+1 cho mọi 0 <= i < n. Ta phải tìm độ cao cao nhất của một điểm.

Ví dụ: gain = [-4,2,6,1,-6], kết quả là 5 vì các độ cao lần lượt là [0,-4,-2,4,5,-1], max = 5.

Giải thuật

1. maximum := 0
2. run_alt := 0
3. Với mỗi delta trong gain:
   • run_alt += delta
   • maximum := max(maximum, run_alt)
4. Trả về maximum

Ví dụ (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))

Input

[-4,2,6,1,-6]

Output

5