ZeroJudge 解題筆記：c435. MAX ! MAX ! MAX !

作者：王一哲
日期：2025年8月15日


ZeroJudge 題目連結：c435. MAX ! MAX ! MAX !

解題想法

假設陣列 d 共有 n 項，用變數 small 記錄目前的最小值，變數 large 記錄目前的最大值，兩者預設值皆為 d[0]。由左向右掃過 d[1] ~ d[n-1]，如果 d[i] 小於 small，找到新的最小值，可能有新的答案；如果 d[i] 大於 large，重設 small 及 large。

Python 程式碼

使用時間約為 92 ms，記憶體約為 15.6 MB，通過測試。

n = int(input())  # 數量 n
d = list(map(int, input().split()))  # 要檢測的資料 d
small = large = d[0]  # 目前的最小值 small、最大值 large，先預設為 d[0]
ans = tmp = 0  # 答案 ans，暫存差距用的 tmp，先預設為 0
for i in range(1, n):  # 依序檢測 d[1] ~ d[n-1]
    if d[i] < small:  # 如果 d[i] 小於 small
        small = d[i]  # 更新 small 為 d[i]
        ans = max(large - small, tmp)  # ans 更新為 large - small 及 tmp 較大者
    elif d[i] > large:  # 如果 d[i] 大於 large
        tmp = ans  # 先將 ans 暫存到 tmp
        small = large = d[i]  # 更新 small、large 為 d[i]
# end of for loop
print(ans)  # 印出答案

C++ 程式碼

使用時間約為 15 ms，記憶體約為 344 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 數量 n
    int d; cin >> d;  // 要檢測的資料 d
    int small = d, large = d;  // 目前的最小值 small、最大值 large，先預設為 d[0]
    int ans = 0, tmp = 0;  // 答案 ans，暫存差距用的 tmp，先預設為 0
    for(int i=1; i<n; i++) {  // 依序檢測第 2 ~ n 個數字
        cin >> d;  // 讀取一個數字
        if (d < small) {  // 如果 d 小於 small
            small = d;  // 更新 small 為 d
            int diff = large - small;  // 差距
            if (diff > tmp) ans = diff;  // ans 更新為 large - small 及 tmp 較大者
        } else if (d > large) {  // 如果 d 大於 large
            tmp = ans;  // 先將 ans 暫存到 tmp
            small = d; large = d;  // 更新 small、large 為 d
        }
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}