[CSP-X 2023 山东] 赚钱

知识点

线性扫描、前缀最小值

解题思路

顺序枚举卖出城市j，用此前城市的最低价格作为买入价。先用当前卖价减此前最低价更新答案，再把当前价格纳入最低价。答案用第一对城市初始化，不能初始化为0。

正确性说明

在固定卖出城市j时，所有合法买入城市恰是j之前的城市，其中最低价使利润最大。对每个卖出城市取最优再求全局最大，覆盖所有合法交易。

易错点

必须买卖一次，全部降价时答案为负；不能在同一城市交易；先更新利润再更新最低价；使用64位整数。

复杂度

时间O(n)，额外空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;long long low,x,ans=LLONG_MIN;cin>>low;for(int i=1;i<n;++i){cin>>x;ans=max(ans,x-low);low=min(low,x);}cout<<ans<<'\n';}