2018-09-02 08:35:10 +00:00
|
|
|
|
# [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/)
|
2019-11-05 08:14:39 +00:00
|
|
|
|
|
|
|
|
|
|
update: LeetCode六道股票买卖题目总结见我的博客文章[动态规划之股票买卖系列](https://shusentang.github.io/2019/11/03/Buy-and-Sell-Stock/)
|
2018-09-02 08:35:10 +00:00
|
|
|
|
# 思路
|
|
|
|
|
|
题目的意思就是求数组prices中，prices[i]-prices[j]的最大值,其中i > j。
|
|
|
|
|
|
因此prices[j]肯定是prices[i]之前的元素中最小的那一个，所以从前往后遍历，并用min_price记录当前位置前的元素中最小的一个。
|
|
|
|
|
|
另外注意单独判断空数组的情况。
|
|
|
|
|
|
# C++
|
2019-09-13 15:08:41 +00:00
|
|
|
|
``` C++
|
2018-09-02 08:35:10 +00:00
|
|
|
|
class Solution {
|
|
|
|
|
|
public:
|
|
|
|
|
|
int maxProfit(vector<int>& prices) {
|
|
|
|
|
|
if(prices.size() == 0) return 0;
|
|
|
|
|
|
int max_profit = 0, min_price = prices[0];
|
|
|
|
|
|
for(int i = 1; i < prices.size(); i++){
|
|
|
|
|
|
if(prices[i] - min_price > max_profit) max_profit = prices[i] - min_price;
|
|
|
|
|
|
if(min_price > prices[i]) min_price = prices[i];
|
|
|
|
|
|
}
|
|
|
|
|
|
return max_profit;
|
|
|
|
|
|
}
|
|
|
|
|
|
};
|
|
|
|
|
|
```
|
