会津大学オンラインジャッジ 問ＡＬＤＳ1＿1Ｄ

Getting Started - Maximum Profit

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_D

儲かることしか考えない人間心理の盲点を突いた問題です。
r日目以降に売ることを考えた場合、r日目以降の最大値とr-1日目までの最小値を角突き合わせればよいだけです。
というわけでr日目までの最小値をminsに保存してあとは逆向きにr+1日目以降の最大値と差額を計算します。
儲からない場合があるのがこの問題の盲点です。


#include<stdio.h>
#include<algorithm>

const int LIMIT=200001;
int Rs[LIMIT],mins[LIMIT];

int main(){
int n,ans,vMin;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&Rs[i]);
if(i==0){
vMin=Rs[0];
}else{
vMin=std::min(Rs[i],vMin);
}
mins[i]=vMin;
}
int vMax=Rs[n-1];
ans=Rs[n-1]-mins[n-2];
for(int i=n-2;i>=0;i--){
ans=std::max(ans,vMax-mins[i]);
vMax=std::max(Rs[i],vMax);
}
printf("%d\n",ans);
}