题解 | 买卖股票的最好时机(一)

• 数据量为1E5，那么使用O(n2)O(n2)的解法大概率会超时。
• 分析问题，只要在股票每一天价格中记录最大正向价格差即可，即读入一个价格，如果当前价格比前一天的价格还低则以当前价格暂时做为买入价格，否则记录正向价格差，那么在次过程中的使用一个变量dp记录最大正向价格差即可。这样时间复杂度就是O(n）O(n）,而空间复杂度可以做到O(1)O(1)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
     cin>>n;
     int dp = INT_MIN;//用于记录最大正向价格差
     int v;
     int tmp = INT_MAX;//用于记录过程中的买入价格。
     for(int i = 0; i < n; ++i){
        scanf("%d", &v);
        if(v < tmp) tmp = v;
            dp = max(dp, v-tmp);        
     }
    cout<<(dp<0? 0:dp)<<endl;
    return 0;
}