青岛快速网站排名_东莞网站提升排名_知名seo公司_千度seo

这题之前贪心部分做过，找到前面股票的最低值，每次买卖股票都与之前的最低值进行交易，再找到利润最大的那次交易。

class Solution {
public:int maxProfit(vector<int>& prices) {int pre_min = INT_MAX, ans = 0;for(int price : prices){ans = max(ans, price - pre_min);pre_min = min(pre_min, price);}return ans;}
};

采用动态规划的思想来解决这题，每天有两个状态，持有股票和不持有股票，因此dp数组应该是二维的，dp[i][0]/dp[i][1]表示第i天持有/不持有股票时所拥有的最大利润。递推公式是，当天可以不买股票和买股票，持有股票的利润是在昨天持有股票的利润（今天不买）和今天买股票的开销中取最大值（因为只能买卖一次），$dp[i][0]=max(dp[i-1][0],-prices[i])$；对于不持有股票，也有当天选择买和不买股票$dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])$

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// dp[i][0]/[1]表示第i天持有/不持有股票得到利润vector<vector<int>> dp(n, vector<int>(2));dp[0][0] = -prices[0];for(int i=1; i<n; ++i){dp[i][0] = max(dp[i-1][0], -prices[i]); // 只能买卖一次dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);}return dp[n-1][1];}
};

从递归公式发现当前值dp[i][0/1]只与前一天的dp值有关，我们可以进行空间复杂度的优化，只采用两个变量。

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// buy/sale表示第i天持有/不持有股票得到利润int buy = -prices[0], sale = 0;for(int i=1; i<n; ++i){int tmp = buy;buy = max(buy, -prices[i]); // 只能买卖一次sale = max(sale, tmp + prices[i]);}return sale;}
};

这题在上一题的基础上去除掉了只能买卖一次的限制，贪心的做法是 只要股票涨了就卖，代码如下：

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

采用动态规划的思想解决，与上一道题类似，每天有两个状态，持有股票和不持有股票，dp数组的含义相同，不过由于此时不止可以买卖一次，所以dp方程需要进行修改，$dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])$，dp[i][1]与上一题一样

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2));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][1], dp[i-1][0] + prices[i]);}return dp[n-1][1];}
};

空间复杂度优化：

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// buy/sale表示第i天持有/不持有股票得到利润int buy = -prices[0], sale = 0;for(int i=1; i<n; ++i){int tmp = buy;buy = max(buy, sale-prices[i]); // 只能买卖一次sale = max(sale, tmp + prices[i]);}return sale;}
};

这题买卖次数限定为最多两次，对于每天就有买卖一/两 次持有/非持有股票的四个状态,他们之间的状态转移很容易分析。直接上代码：

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// dp[i][0/1/2/3] 分别表示第一次买卖后持有/非持有股票、第二次买卖后持有/非持有股票vector<vector<int>> dp(n, vector<int>(4));dp[0][0] = -prices[0];dp[0][2] = -prices[0];for(int i=1; i<n; ++i){dp[i][0] = max(dp[i-1][0], -prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]);dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i]);}return dp[n-1][3];}
};

空间复杂度优化代码如下，这个代码有个细节，在售卖的时候sell1 = max(sell1, buy1 + prices[i])使用的是当天的持有状态buy1而不是存储前一天buy1的临时变量。可以理解为今天买入股票又卖出股票，等于没有操作，保持昨天卖出股票的状态了。

class Solution {
public:int maxProfit(vector<int>& prices) {// 分别表示第一次买卖后持有/非持有股票、第二次买卖后持有/非持有股票int buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0;for(int i=1; i<prices.size(); ++i){buy1 = max(buy1, -prices[i]);sell1 = max(sell1, buy1 + prices[i]);buy2 = max(buy2, sell1 - prices[i]);sell2 = max(sell2, buy2 + prices[i]);}return sell2;}
};