*121. 买卖股票的最佳时机

leetcode题目地址

贪心

找左侧最小值、右侧最大值（与最小值求差最大），求差即为最大利润。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

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

*动态规划

思路

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

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

leetcode题目地址

贪心

遍历价格列表，取记录最低价和当前价格比较取最小的赋值为新的最低价。

若当前价格卖出可以盈利则在当天卖出，同时再在当天买入，继续向后找最低价格。

tips: 题目提到可以在同一天进行买入和卖出，因此可以在当天卖出后再买入。

思路

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// c++
class Solution {
public:int maxProfit(vector<int>& prices) {int low = INT_MAX;int res = 0;for(int i=0; i<prices.size(); i++){low = min(low, prices[i]);if(prices[i]-low>0){res += prices[i]-low;low = prices[i];}}return res;}
};

*动态规划

和上题思路类似，上一题只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

本题可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。

第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i - 1][1] - prices[i]。

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

*123. 买卖股票的最佳时机 III

leetcode题目地址

一共四种状态，第一次买入/持有、第一次卖出/不持有、第二次买入/持有、第二次卖出/不持有。

分配四列来记录这四种状态，dp[i][j]是指在第i天的第j个状态时的最大利润。

思路

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(5, 0));// 不操作dp[0][0] = 0;// 第一次买入/持有dp[0][1] = -prices[0];// 第一次卖出/不持有dp[0][2] = 0;// 第二次买入/持有dp[0][3] = -prices[0];// 第二次卖出/不持有dp[0][4] = 0;for(int i=1; i<prices.size(); i++){// dp[i][0] = 0;dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1]);dp[i][2] = max(dp[i-1][1]+prices[i], dp[i-1][2]);dp[i][3] = max(dp[i-1][2]-prices[i], dp[i-1][3]);dp[i][4] = max(dp[i-1][3]+prices[i], dp[i-1][4]);}int len=prices.size()-1;return dp[len][4];}
};