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

用lastMin记录遍历到的i之前的出现的最小值

1.当 p[i]<=lastMin，说明p[1~i]上的最大收益和p[1~i-1]上一样， f[i] = f[i-1]

2.当p[i]>lastMin，说明有可能产生更大的收益，f[i] = max(f[i-1], p[i]-lastMin)

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5+10;
int n;
int prices[N];
int dp[N];  //dp[i]表示 prices[1:i]上的最大收益
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &prices[i]);
    }
    dp[1] = 0;
    int lastMin = prices[1];
    for(int i = 2; i <= n; i++){
        if(prices[i]<=lastMin){
            dp[i] = dp[i-1];
            lastMin = prices[i];
        }else{
            dp[i] = max(dp[i-1], prices[i]-lastMin);
        }
    }
    printf("%d", dp[n]);
    return 0;
}
// 64 位输出请用 printf("%lld")