LeetCode 122 买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

示例：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

贪心

相较于121.买卖股票的最佳时机，本题的主要区别在于：考虑的不只是单次买卖股票的情形，可以对一只股票多次进行买卖，需要求解的是整体的最优化。

要想实现最大的利润，那么本质上就是在序列中寻找单调区间，将序列中的全部单调增区间的区间长度相加，就是最大的利润值。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1) return 0;
        int start=prices[0],last=start;
        int res=0;
        for(int i=1;i<n;i++){
            if(prices[i]>=last){
                last=prices[i];
            }else{
                res+=last-start;
                start=prices[i];
                last=start;
            }
        }
        res+=last-start;
        return res;
    }
};

更加高效的贪心实现：在本题中，交易的次数是不存在限制的，因此完全可以采取如下策略。

对于 i 和 i-1 只要 prices[i]>prices[i-1] 那么就在 i-1 买入，在 i 天卖出，也就是赚取全部能够赚取的利润。

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

当然，寻找单调递增区间的操作基于暴力法也是能够实现的。

动态规划

此处使用动态规划进行求解存在两个要点：首先是动态规划数组的定义，其次是动态规划数组的定义（本质上还是如何对问题进行划分）

动态规划数组的定义：定义一个二维的动态规划数组 dp[n][2] ，其中 dp[i][0] 表示在第 i 持有股票所拥有的现金， dp[i][1] 表示在第 i 天不持有股票所能获得最多的现金。关于现金的含义：在初始状态现金为0，那么在某天买入后现金是 -prices[i] ，只有在股票卖出后当前持有的现金才会发生改变。
动态规划数组的推导：

对于 dp[i][0] 的推导：本质上还是针对于前一天的情形进行推导

前一天持有的情形，在第 i 天无需对股票进行操作 dp[i][0]=dp[i-1][0]
前一天不持有的情形， dp[i][0]=dp[i-1][1]-prices[i] 也就是在第 i 天进行了股票的买入

对于 dp[i][1] 的推导：在前一天持有或不持有两种情形

前一天持有的情形，在第 i 天对股票进行卖出操作 dp[i][1]=dp[i-1][0]+prices[i]
前一天不持有的情形， dp[i][1]=dp[i-1][1] 也就是在第 i 天不对股票进行操作

动态规划数组的初始化：对于第0天的情形，不持有股票现金为0，持有股票现金为 -prices[0] ，那么 dp[0][0]=-prices[0],dp[0][1]=0
动态规划数组的遍历顺序：从前向后遍历

代码实现：

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

改为滚动数组实现：

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

Mark's blogs

LeetCode-122-买卖股票的最佳时机II

LeetCode 122 买卖股票的最佳时机II

贪心

动态规划