1732. 找到最高海拔 Find the Highest Altitude

问题描述

这个问题可以使用前缀和 prefix sum 的算法, 但是是逆着来的, 给出的是前缀和数组, 我们需要得到 原先的数组.

#![allow(unused)]
fn main() {
// Prefix sum
pub fn largest_altitude1(gain: Vec<i32>) -> i32 {
    debug_assert!(!gain.is_empty());
    let mut last_altitude = 0;
    let mut highest = 0;
    for altitude in gain {
        last_altitude += altitude;
        highest = highest.max(last_altitude);
    }
    highest
}
}

时间复杂度是 O(n), 空间复杂度是 O(1).