- 1、题目描述:
-3、 设计思想:
详细操作流程看下图:
-4、视频讲解链接B站视频讲解
-5、代码:
c++版本:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 两次交易所能获得的最大收益 * @param prices int整型vector 股票每一天的价格 * @return int整型 */ int maxProfit(vector<int>& prices) { // write code here if (prices.size() == 0) return 0; /* 5个状态:1)不操作2)第一次购买3)第一次卖出4)第二次购买5)第二次卖出 dp[i][j]代表第i天状态为j时产生的最大收益 */ int dp[200005][5]={0}; //初始化 dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (int i = 1; i < prices.size(); i++) { dp[i][0] = dp[i - 1][0]; //其中dp[i][1]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); //其中dp[i][2]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小 dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]); //其中dp[i][3]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小 dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]); //其中dp[i][4]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小 dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]); } return dp[prices.size() - 1][4]; } }; ///空间复杂度的优化版本 int maxProfit(vector<int>& prices) { // write code here if (prices.size() == 0) return 0; /* 5个状态:1)不操作2)第一次购买3)第一次卖出4)第二次购买5)第二次卖出 dp[i][j]代表第i天状态为j时产生的最大收益 */ //初始化 int dp0 = 0; int dp1 = -prices[0]; int dp2 = 0; int dp3 = -prices[0]; int dp4 = 0; for(int i = 1;i < prices.size();i ++){ dp0 = dp0; dp1 = max(dp1, dp0 - prices[i]); dp2 = max(dp2,dp1 + prices[i]); dp3 = max(dp3,dp2 - prices[i]); dp4 = max(dp4,dp3 + prices[i]); } return dp4; }
Java版本:
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 两次交易所能获得的最大收益 * @param prices int整型一维数组 股票每一天的价格 * @return int整型 */ public int maxProfit (int[] prices) { // write code here if (prices.length == 0) return 0; /* 5个状态:1)不操作2)第一次购买3)第一次卖出4)第二次购买5)第二次卖出 dp[i][j]代表第i天状态为j时产生的最大收益 */ int [][]dp = new int[prices.length][5]; //初始化 dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (int i = 1; i < prices.length; i++) { dp[i][0] = dp[i - 1][0]; //其中dp[i][1]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); //其中dp[i][2]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小 dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]); //其中dp[i][3]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小 dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]); //其中dp[i][4]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小 dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]); } return dp[prices.length - 1][4]; } }
Python版本:
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # 两次交易所能获得的最大收益 # @param prices int整型一维数组 股票每一天的价格 # @return int整型 # class Solution: def maxProfit(self , prices ): # write code here n = len(prices) if n == 0:return 0 ''' 5个状态:1)不操作2)第一次购买3)第一次卖出4)第二次购买5)第二次卖出 dp[i][j]代表第i天状态为j时产生的最大收益 ''' dp = [[0]*5 for i in range(n)] #初始化 dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for i in range(1, n): dp[i][0] = dp[i-1][0] #其中dp[i][1]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) #其中dp[i][2]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小 dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]) #其中dp[i][3]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小 dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]) #其中dp[i][4]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小 dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]) return dp[n - 1][4]
JavaScript版本:
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 两次交易所能获得的最大收益 * @param prices int整型一维数组 股票每一天的价格 * @return int整型 */ function maxProfit( prices ) { // write code here if (prices.length == 0) return 0; /* 5个状态:1)不操作2)第一次购买3)第一次卖出4)第二次购买5)第二次卖出 dp[i][j]代表第i天状态为j时产生的最大收益 */ let dp = new Array(prices.length) for(let i = 0;i < prices.length;i++) dp[i] = new Array(5).fill(0) //初始化 dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (let i = 1; i < prices.length; i++) { dp[i][0] = dp[i - 1][0]; //其中dp[i][1]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); //其中dp[i][2]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小 dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]); //其中dp[i][3]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小 dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]); //其中dp[i][4]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小 dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]); } return dp[prices.length - 1][4]; } module.exports = { maxProfit : maxProfit };