作者：

链接：http://proprogrammar.com:443/article/856

声明：请尊重原作者的劳动，如需转载请注明出处

剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

难度：中等；标签：动态规划；编程语言：C++

我的解法

int maxProfit(vector<int>& prices) {
        int res = 0;
        stack<int> s;

        for(int i = 0; i < prices.size(); i++){
            if(s.empty() || prices[i] < s.top()){
                s.push(prices[i]);
            }
            if(prices[i] > s.top()){
                res = max(res, prices[i] - s.top());
            }
        }

        return res;
    }

这里用s保存一个递减栈，保存当前最小值（买入价格最低），如果价格上升，就试着卖一下，最后返回卖出价最高的；不好理解，画个图理解一下会好点

如图有5天，s栈顶值，结果如图，在第3，5天价格上升，虽然第4天最小值较小，但由于第3天上升较多，所以在第2天买，第3天卖

其它解法

这里的s可以去掉，因为只要最小的栈顶值，所以有下面的解法

int maxProfit(vector<int>& prices) {
        int cost = INT_MAX, profit = 0;
        for(int price : prices) {
            cost = min(cost, price);
            profit = max(profit, price - cost);
        }
        return profit;
    }

而且把每天的价格变化也省了，因为如果价格下降，相减为负，求max不可能取到负值，不过没有上面的代码，这里更不好理解

亲爱的读者：有时间可以点赞评论一下