动态十九：买卖股票的最佳时机

题目地址： https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
题目描述： 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

参考代码：

class Solution {
public:
    //贪心
    int maxProfit(vector<int>& prices) {
        int result = 0;
        int minVaule = INT_MAX;
        for (int i = 0; i<prices.size(); i++) {
            minVaule = min(minVaule, prices[i]);
            if (i > 0) {
                result = max(result, prices[i] - minVaule);
            }
        }
        return  result;
    }
    
    //动态
    int maxProfit1(vector<int>& prices) {
        int result = 0;
        if (prices.size() == 0) {
            return  result;
        }
        //dp[i][0] 第i天 持有股票  dp[i][1] 第i天 不持有
        
        // 状态迁移
        vector<vector<int>> dp = vector<vector<int>> (prices.size(),vector<int>(2,0));
    
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i<prices.size();i++) {
            dp[i][0] = max(dp[i-1][0],-prices[i]);// 只能买一次
//            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]); // 可以买多次
            dp[i][1] = max(dp[i-1][1],prices[i] + dp[i-1][0]);
            
        }
        return  dp[prices.size()-1][1];
    }

};

参考链接： https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.md