[算法题]买卖股票的最好时机(一)

题目链接: 买卖股票的最好时机(一)

利用贪心, 并且遍历求解, 从前往后遍历, 每遍历到一个位置就在该天卖出, 利用一个变量保存在第 i 天卖出时, 在区间 [0, i-1] 中的最小买入价格, 再用一个变量保存每次卖出的最大值, 不断遍历更新卖出的最大值即可.

图示:

题解代码:

#include <iostream>
using namespace std;

int main() 
{
    int n = 0;
    cin >> n;
    int max_price = 0; //最高收益
    int min_price = 0; //[0, i-1]区间的最小买入价格
    int val = 0;
    for(int i = 0; i < n; ++i)
    {
        cin >> val;
        if(i == 0)
        {
            min_price = val;
        }
        else
        {
            max_price = max(max_price, val - min_price); //更新最高收益
            min_price = min(min_price, val); //更新[0, i-1]区间的最小买入价格
        }
    }
    cout << max_price << endl;
    return 0;
}