题解 | #买卖股票的最好时机#

动态规划
dp[i][0]代表下标为i天的时候，手上没有股票的最大收益
dp[i][1]代表i天的时候手上有股票最小收益是多少

初始状态dp[0][0]=0,dp[i][1]=prices[0]

状态转移方程：
dp[i][0] = max(dp[i-1][0], prices[i]-dp[i-1][1]);
dp[i][1] = min(dp[i-1][1], prices[i]);

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */

    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        int dp[prices.size()][2];
        dp[0][0] = 0;
        dp[0][1] =  prices[0];
        for(int i = 1;i < prices.size();i ++){
            dp[i][0] = max(dp[i-1][0],prices[i] - dp[i-1][1]);
            dp[i][1] = min(dp[i-1][1],prices[i]);
        }
        return dp[prices.size()-1][0];
    }
};

建立天数和股票值得映射关系，推导

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //股票价格和天数i建立键值对关系，排序比较较大和较小值，小值的天数小于较大数说明就是最大收益
        if(prices.size() == 1) return 0;
        multimap<int, int> mm;
        for (size_t i = 0; i < prices.size(); i++)
            mm.insert(make_pair(prices[i], i));

        //首往后走
        multimap<int, int>::iterator it = mm.begin();
        multimap<int, int>::reverse_iterator rit = mm.rbegin();
        while (it->second > rit->second)
                it++;
        if(it->second < rit->second)
            return rit->first - it->first>0?rit->first - it->first:0;

        //尾往前走
        it = mm.begin();
        rit = mm.rbegin();
        while (it->second > rit->second)
                rit++;
        if(it->second < rit->second)
            return rit->first - it->first>0?rit->first - it->first:0;
        return 0;
    }
};

双指针法:通过14/19

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //双指针法
        int max = 0;
        int i = 0, j = prices.size() - 1;
        while (i < j) {
            if (prices[i] <= prices[j])
                max = prices[j] - prices[i] > max ? prices[j] - prices[i] : max;
            if (prices[i + 1] < prices[i] || prices[j - 1] > prices[j]) {
                i = prices[i + 1] < prices[i] ? i + 1 : i;
                j = prices[j - 1] > prices[j] ? j - 1 : j;
            }
            else
                i++;
        }
        return max;
    }
};