ZeroJudge 解題筆記：f935. 消失的二十年 - 續

作者：王一哲
日期：2025年10月31日


ZeroJudge 題目連結：f935. 消失的二十年 - 續

解題想法

最低價 min_price 預設為第 0 天的價格，最大獲利 max_proift 預設為 0。依序讀取第 1 天到最後一天的價格 price，如果當天賣出的獲利大於目前的 max_profit，更新 max_profit、最低買價 buy、最高賣價 sell； 如果 price 小於 min_price，更新 min_price。最後如果找不到低於 min_price 的𧶠價，max_profit 等於 0，輸出 0 -1 -1； 反之，輸出 max_profit buy sell。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 126.7 MB，通過測試。

prices = list(map(int, input().split()))  # 每天的價格
min_price = prices[0]  # 最低價格，預設為第 0 天的價格
max_profit = 0  # 最大獲利，預設為 0
buy = sell = -1  # 最大獲利對應的最低買價、最高賣價，預設為 -1
for price in prices[1:]:  # 依序讀取讀取第 1 天到最後一天的價格
    if price - min_price > max_profit:  # 更高的獲利
        max_profit = price - min_price  # 更新最大獲利
        buy = min_price  # 更新最低買價
        sell = price  # 更新最高賣價
    elif price < min_price:  # 更低的價格
        min_price = price  # 更新最低價格
if max_profit == 0: print("0 -1 -1")
else: print(f"{max_profit:d} {buy:d} {sell:d}")

C++ 程式碼

使用時間約為 0.1 s，記憶體約為 84 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int price; scanf("%d", &price);
    int min_price = price, max_profit = 0, buy = -1, sell = -1;
    while(scanf("%d", &price) != EOF) {
        if (price - min_price > max_profit) {
            max_profit = price - min_price;
            buy = min_price;
            sell = price;
        } else if (price < min_price) {
            min_price = price;
        }
    }
    if (max_profit == 0) printf("0 -1 -1\n");
    else printf("%d %d %d\n", max_profit, buy, sell);
    return 0;
}