题目链接: 买卖股票的最好时机(一)
利用贪心, 并且遍历求解, 从前往后遍历, 每遍历到一个位置就在该天卖出, 利用一个变量保存在第 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;
}