こんにちは！ mnbd（@mnbbbbbd）です。
AIZU ONLINE JUDGEの「ALDS1_1_D 最大の利益」を解いてみましたので、その回答と解説をご紹介いたします。
プログラミング初心者なので、もっといい回答があるに違いありません。
あくまでも「動作はする」サンプルとしてご覧ください。
問題文
FX取引では、異なる国の通貨を交換することで為替差の利益を得ることができます。例えば、１ドル100円の時に 1000ドル買い、価格変動により 1ドル 108円になった時に売ると、(108円 − 100円) × 1000ドル = 8000円の利益を得ることができます。
ある通貨について、時刻 tt における価格 Rt (t=0,1,2,,,n−1)が入力として与えられるので、価格の差 Rj−Ri (ただし、j>i とする) の最大値を求めてください。
入力
最初の行に整数 n が与えられます。続く n 行に整数 Rt(t=0,1,2,,,n−1) が順番に与えられます。出力
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D
最大値を１行に出力してください。
解答
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int r[n];
for(int i = 0; i < n; i++) {
cin >> r[i];
}
// int maxv = r[1] - r[0];
// for(int i = 1; i <= n - 1; i++) {
// for(int j = 0; j <= i - 1; j++) {
// maxv = max(maxv, r[i] - r[j]);
// }
// }
int minv = r[0];
int maxv = INT_MIN;
for(int i = 1; i <= n - 1; i++) {
maxv = max(maxv, r[i] - minv);
minv = min(minv, r[i]);
}
cout << maxv << endl;
return 0;
}感想
この問題は自力ではわからなくて、一般解説を読みました。
アルゴリズムが載っていますので、それをC++で書き直したものになります。
コメントアウトしてるコードですと、時間オーバーで合格できません。
正答率が30%なのでかなり難易度高めですね。
個人的に理解できているとは思えません。
AIZU ONLINE JUDGEの「アルゴリズムとデータ構造入門」のトピック1を終了しましたが、「プログラミング入門」より難しさを感じています。
まとめ
AIZU ONLINE JUDGEの「ALDS1_1_D 最大の利益」を解いてみましたので、その回答と解説をご紹介いたします。
以上です。
読んでいただきありがとうございました！