best-time-to-buy-and-sell-stock

Best Time to Buy and Sell Stock – LeetCode 121

Problem

Description

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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Answer

Original

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int buy = INT_MAX, margin = 0;
        for(unsigned i = 0; i != prices.size(); ++i){
            if(prices[i] < buy) buy = prices[i];
            else if((prices[i] - buy) > margin) margin = prices[i] - buy;
        }
        return margin;
    }
};

思路

存储到目前的最低值，同时计算当前为止的最高收益。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$6$ ms，排名$69.92\%$

Better

思路

使用动态规划，用局部最优和全局最优解法。思路是维护两个变量，一个是到目前为止最好的交易，另一个是在当前一天卖出的最佳交易（也就是局部最优）。递推式是$local[i+1]=max(local[i]+prices[i+1]-price[i],0)$和$global[i+1]=max(local[i+1],global[i])$。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$6$ ms，排名$69.92\%$

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int local = 0;
        int global = 0;
        for(unsigned i = 0;i != prices.size(); ++i){
            local = max((local + prices[i+1] - prices[i]), 0);
            global = max(local, global);
        }
        return global;
    }
};