AIZU ONLINE JUDGEの『ALDS1_1_D:Maximum Profit』を解いたので記録。


【目次】
問題概要
解き方
実装




問題概要


ある通貨について時刻tにおける価格、RtRt (t=0,1,2,,,n1t=0,1,2,,,n1)が入力として与えられるので、価格の差 RjRiRjRi (ただし、j>ij>i とする) の最大値を求めてください。

FX取引で為替差で利益を求めるという問題。



解き方


何も考えずに書くと二重ループを使って以下のように解いていくのが無難...。

for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++i)
// jとiの差が最大になるものを求める
}

ただこれだと計算量が大きくなるのでループを一つにする方法を考える。

購入値が安くなった時にだけ、購入価格を更新することでループの数を減らせそうだ。



実装


#include <iostream>

using namespace std;

int main(void){
int n;
cin >> n;
int *rt = new int[n];
for(int i=0; i<n; ++i){
cin >> rt[i];
}
long long buyPrice = rt[0];
long long varitation = rt[1] - rt[0];

for (int i=1; i<n; ++i){
if (varitation < rt[i] - buyPrice){
varitation = rt[i] - buyPrice;
}
if (buyPrice > rt[i]){
buyPrice = rt[i];
}
}

cout << varitation << endl;

return 0;
}