f935 - 消失的二十年 - 續
題目描述
題目要求找出在給定股票價格序列中，買入和賣出一次所能獲得的最大利潤，以及對應的買入和賣出價格。如果無法獲利，則輸出 -1 -1。
解題思路
此題可以使用貪心演算法解決。我們只需要遍歷股票價格序列一次，記錄到目前為止的最低買入價，並計算當前價格與最低買入價之間的差值。如果差值大於目前的最大利潤，則更新最大利潤、買入價和賣出價。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int n,ma=-1000000,mi=1000000,ans,l=-1,r=-1,tl=-1;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
while(n=read()){
if(mi>n)mi=l=n;
if(ans<n-mi)ans=n-mi,r=n,tl=l;
}
write(ans);
if(ans){
putchar_unlocked(' ');
write(tl);
putchar_unlocked(' ');
write(r);
}
else{
puts(" -1 -1");
}
}