程式交易 (APCS 2022-01 初級)

小明最近想要用程式做股票交易。給定一支股票的歷史價格 \(a[1], a[2], \ldots, a[n]\)，他的投資策略如下：

1. 同一時間最多只持有一張股票，並會在時間點 \(1\) 花 \(a[1]\) 買進。
2. 若當下持有股票，且該股票的買進價格為 \(x\)，當遇到價格 \(y\) 滿足 \(y - x \ge D\) 時即賣出，獲得利潤 \(y - x\)。
3. 若當下沒有持有股票，且上一次的賣出價格為 \(x\)，當遇到價格 \(y\) 滿足 \(y \le x - D\) 時即買進。

請輸出依上述規則買賣後所得到的總利潤。若交易結束時仍持有股票，則不考慮該股票買進的成本（直接無視該張股票）。

輸入格式

第一行輸入兩個正整數 \(n\) 與 \(D\)。

第二行有 \(n\) 個正整數，依序代表每個時間點的股票價格。

限制

• \(1 \le n, D \le 100\)
• \(1 \le a[i] \le 100\)

輸出格式

輸出一個整數，代表總利潤。

評分說明

每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過的測試資料筆數給分。其中：

• 第 1 子題組（\(50\) 分）：\(n = 3\)。
• 第 2 子題組（\(50\) 分）：無額外限制。

範例輸入 1

3 10
50 20 45

範例輸出 1

0

（說明）在時間點 \(1\) 以 \(50\) 買進。之後價格 \(20\)、\(45\) 都未達 \(50 + 10 = 60\)，無法賣出；交易結束仍持有，無視該股票，利潤為 \(0\)。

範例輸入 2

6 10
30 20 45 38 10 20

範例輸出 2

25

（說明）以 \(30\) 買進；遇到 \(45\)（\(45 - 30 = 15 \ge 10\)）賣出得 \(15\)；之後遇到 \(10\)（\(\le 45 - 10 = 35\)）買進；遇到 \(20\)（\(20 - 10 = 10 \ge 10\)）賣出得 \(10\)。總利潤 \(15 + 10 = 25\)。

題目來源

APCS 2022 年 1 月實作題第 1 題。

• ZeroJudge h081