問題
Maximum Profit
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_D&lang=ja
考え方
ある通貨について、時刻 t における価格 Rt (t=0,1,2,,,n−1)が入力として与えられるので、価格の差 Rj−Ri (ただし、j>i とする) の最大値を求めてください。
問題文を数式に置き換えていく
for(int j = 1; j < n-1; j++){
for(int i = 0; i <= j-1; i++){
max_profit = max(max_profit, R[j] - R[i]);
}
}
改良
for(int j = 1; j < n-1; j++){
max_profit = max(max_profit, R[j] - min_value);
min_value = min(min_value, R[j]);
}
コード
#include <stdio.h>
#include <limits.h>
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int main(void)
{
int n, max_profit, min_value;
int R[2000000];
/* 値の受け取り */
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &R[i]);
/* 初期化 */
max_profit = INT_MIN;
min_value = R[0];
/* 最大利益の計算 */
for (int j = 1; j < n; j++)
{
max_profit = max(max_profit, R[j] - min_value);
min_value = min(min_value, R[j]);
}
/* 出力 */
printf("%d\n", max_profit);
return 0;
}
所感
min_value = R[0];
の設定のところとか、ループ内でやろうとして混乱してた。
何を結果としてほしいのか、問題文から言語化していく。
所要時間70分