LeetCode 121. Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

解析：买卖股票的最佳时机，给定了一组数值，表示每天的股票价格，选择合适的买卖时机使得利润最大。采用动态规划的思路，采用一个数值保存截止到当前位置的最小值，然后计算当前位置上的数值与最小值的差值，然后选择最大的利润。代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty())
            return 0;
        int max_profit = 0;
        int buy = INT_MAX;
        for(auto stock : prices)
        {
            buy = min(buy, stock);
            max_profit = max(max_profit, stock - buy);
        }
        return max_profit;
    }
};