代码随想录训练营第四十九天| ● 121. 买卖股票的最佳时机 ● 122.买卖股票的最佳时机II

2023-12-31 12:05:30

?这道题可用一次遍历完成（贪心思路，选取最小值和最大利润），在遍历过程中记录最小值和结果即可：

int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); i++) {
            low = min(low, prices[i]);
            result = max(result, prices[i] - low);
        }
        return result;
    }

使用动态规划思路：

dp数组有两个维度，[0]表示当前持有股票，[1]表示当前不持有股票，而持有股票是由前面和本次的状态退导出来的，也就是之前就购买了还是这次购买的，选取数值更大的那一个即dp[i][0] = max(dp[i - 1][0], -prices[i]);未持有股票也一样，选取上次的状态和这次卖出后更大的那一个：dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

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

?这道题与上道题的唯一区别是可以多次买入和出售股票，因此在计算当前持有股票时，不应用简单的-prices[i]来判断了，还要使用上一次卖出股票的钱减去这次买入股票的钱来与上一次就持有股票进行判断。

int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len == 0) return 0;
        vector<vector<int>> dp(len, vector<int>(2));
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; 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[len - 1][1];
    }

文章来源:https://blog.csdn.net/Ljhh_h/article/details/135313387
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。