1732. Find the Highest Altitude

題目 / Problem

中文：一位騎自行車的人去公路旅行。這趟旅程有 n + 1 個位於不同海拔的點。騎手從第 0 個點出發，起點海拔為 0。

給你一個長度為 n 的整數陣列 gain，其中 gain[i] 表示第 i 個點到第 i + 1 個點之間的淨海拔變化（可正可負）。請回傳所有點中的最高海拔。

English: A biker goes on a road trip with n + 1 points at different altitudes. The biker starts at point 0 with altitude 0. You are given an integer array gain of length n, where gain[i] is the net altitude change between point i and point i + 1. Return the highest altitude among all points.

Constraints / 約束： - n == gain.length - 1 <= n <= 100 - -100 <= gain[i] <= 100

Worked example / 範例： - Input: gain = [-5, 1, 5, 0, -7] - Altitudes / 各點海拔: [0, -5, -4, 1, 1, -6] - Output: 1（最高點是 1 / the highest point is 1）

名詞解釋 / Glossary

• 前綴和 / prefix sum：把陣列從頭開始一個一個累加起來的「跑動總和」。第 k 個前綴和等於前 k 個元素的總和。本題中，每個點的海拔正好就是 gain 的前綴和。 / A "running total" you build by adding elements one by one from the start. The k-th prefix sum equals the sum of the first k elements — here, each altitude is a prefix sum of gain.
• 累加變數 / running accumulator：一個普通的整數變數，邊走訪陣列邊往上加，用來記住「目前的總和」。 / A plain integer variable that we keep adding to as we scan the array, holding the "sum so far".
• 追蹤最大值 / tracking a maximum：用一個變數記住「到目前為止見過的最大值」，每遇到更大的就更新它。 / Keeping one variable that remembers the largest value seen so far, updated whenever we meet something bigger.

思路

最直接的想法是：先算出每一個點的海拔，存進一個新陣列裡，再從這個陣列裡找最大值。海拔怎麼算？第 0 點是 0，之後每一點的海拔等於前一點海拔加上對應的 gain。換句話說，海拔陣列就是 gain 的前綴和。這個方法完全正確，但它需要額外開一個陣列來存所有海拔，其實有點浪費，因為我們最後只關心「最大值」這一個數字，並不需要把全部海拔都留著。

於是可以優化：我們不必真的把整個海拔陣列建出來。只要用一個累加變數 cur 一路把 gain 加上去，每加一次 cur 就代表「下一個點的海拔」；同時用另一個變數 best 記住目前見過的最高海拔。起點海拔是 0，所以 cur 和 best 都從 0 開始（這很重要，因為答案有可能就是起點 0，像範例 2 那樣）。掃完整個陣列後，best 就是答案。這樣只用了固定的幾個變數，空間複雜度從 O(n) 降到 O(1)。

The most direct idea: compute every point's altitude, store them in a new array, then scan that array for the maximum. How do we get altitudes? Point 0 is 0, and each later altitude is the previous altitude plus the matching gain — in other words, the altitude array is the prefix sum of gain. This works, but it wastes memory: we allocate a whole array yet only ever care about one number, the maximum.

So we optimize. We never need to materialize the full altitude array. Keep a running accumulator cur and add each gain to it; after each addition cur holds the next point's altitude. Keep a second variable best for the highest altitude seen so far. The starting altitude is 0, so both cur and best start at 0 — this matters because the answer can be the starting point itself (see Example 2). After one pass, best is the answer. We use only a couple of variables, dropping space from O(n) to O(1).

逐步走查 / Walkthrough

Input / 輸入: gain = [-5, 1, 5, 0, -7]

Start / 起始: cur = 0, best = 0（代表起點海拔 0 / represents the starting altitude 0）

End / 結束: best = 1 ✅（正好對應海拔序列 [0,-5,-4,1,1,-6] 的最大值 / matches the max of altitudes [0,-5,-4,1,1,-6]）

Solution — C

// 演算法：邊走訪 gain 邊累加成「目前海拔」cur，並用 best 記錄最高海拔。
// Algorithm: scan gain while accumulating into cur (the current altitude),
// and keep best as the highest altitude ever seen. O(n) time, O(1) space.

int largestAltitude(int* gain, int gainSize) {
    // cur 是目前所在點的海拔，從起點 0 開始。
    // cur is the altitude of the current point, starting at 0 (the start point).
    int cur = 0;

    // best 是目前見過的最高海拔，也從 0 開始（因為起點海拔就是 0）。
    // best is the highest altitude so far, also starting at 0 (the start is altitude 0).
    int best = 0;

    // 逐一走訪 gain 的每個元素；i 是陣列索引，從 0 到 gainSize-1。
    // Loop over each element of gain; i is the array index, from 0 to gainSize-1.
    for (int i = 0; i < gainSize; i++) {
        // gain[i] 是陣列第 i 個值，用方括號取值；把它加到 cur 上得到下一個點的海拔。
        // gain[i] reads the i-th value (bracket indexing); add it to cur to get the next altitude.
        cur += gain[i];

        // 如果新的海拔 cur 比目前的最高紀錄還高，就更新 best。
        // If the new altitude cur beats the current record, update best.
        if (cur > best) {
            best = cur;
        }
    }

    // 走完整條路後，best 就是最高海拔，回傳它。
    // After the whole trip, best holds the highest altitude; return it.
    return best;
}

Solution — C++

// 演算法：用一個累加變數 cur 把 gain 變成「目前海拔」，best 追蹤最高海拔。
// Algorithm: accumulate gain into cur (current altitude); best tracks the maximum.
// O(n) time, O(1) extra space.

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        // cur：目前點的海拔，從起點 0 開始。
        // cur: current point's altitude, starting at 0.
        int cur = 0;

        // best：目前見過的最高海拔，從 0 開始（起點海拔為 0）。
        // best: highest altitude so far, starting at 0 (the start is altitude 0).
        int best = 0;

        // range-for 迴圈：依序把 gain 裡的每個值取出來叫做 g（不需要用索引）。
        // Range-for loop: pull each value out of gain in order as g (no index needed).
        for (int g : gain) {
            // 把這段的淨海拔變化加到 cur，cur 就變成下一個點的海拔。
            // Add this segment's net change to cur; cur becomes the next point's altitude.
            cur += g;

            // std::max 回傳兩者中較大的那個，用它更新最高海拔紀錄。
            // std::max returns the larger of the two; use it to update the highest altitude.
            best = max(best, cur);
        }

        // 回傳最高海拔。
        // Return the highest altitude.
        return best;
    }
};

複雜度 / Complexity

• Time / 時間：O(n) — 我們只把 gain 從頭到尾走訪一次，每個元素做固定次數（一次加法、一次比較）的工作，n 是 gain 的長度。 / We scan gain exactly once, doing constant work per element (one addition, one comparison); n is the length of gain.
• Space / 空間：O(1) — 只用了 cur 和 best 兩個固定變數，不論輸入多大都不會增加額外記憶體。 / Only two fixed variables cur and best; memory use does not grow with the input size.

Pitfalls & Edge Cases

• 起始值不能設成負無限或第一個 gain / Don't initialize best to negative infinity or to gain[0]：答案有可能就是起點海拔 0（如範例 2 全程都在 0 以下）。把 cur 和 best 都初始化成 0 才能正確包含起點。 / The answer can be the starting altitude 0 (Example 2 never rises above 0). Initializing both cur and best to 0 correctly includes the start point.
• 別忘了起點也算一個點 / Remember the start counts as a point：海拔點共有 n + 1 個，第一個（海拔 0）必須參與比較，本作法靠 best = 0 自動涵蓋它。 / There are n + 1 points; the first (altitude 0) must be compared. Starting best at 0 covers it automatically.
• 不會溢位 / No overflow risk：最壞情況 100 個元素每個 100，總和最多 10000，遠在 int 範圍內，所以不用擔心整數溢位。 / At worst 100 elements of 100 sum to 10000, well within int range — no overflow concern.
• 累加方向 / Accumulation order：必須把 gain[i] 先加進 cur 再比較，因為比較的是「到達新點之後」的海拔，而不是之前的。 / Add gain[i] to cur before comparing, since we compare the altitude after reaching the new point, not before.