LeetCode/solutions/121. Best Time to Buy and Sell Stock.md

121. Best Time to Buy and Sell Stock

update: LeetCode六道股票买卖题目总结见我的博客文章动态规划之股票买卖系列

思路

题目的意思就是求数组prices中，prices[i]-prices[j]的最大值,其中i > j。
因此prices[j]肯定是prices[i]之前的元素中最小的那一个，所以从前往后遍历，并用min_price记录当前位置前的元素中最小的一个。
另外注意单独判断空数组的情况。

C++

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;
    }
};