沈阳市网站建设报价,wordpress伪装成破解成功,北京网站设计外包公司,广州建筑公司招聘网站LeetCode:123.买卖股票的最佳时机III
123. 买卖股票的最佳时机 III - 力扣#xff08;LeetCode#xff09;
1.思路
将两次买入卖出转化为是否持有的状态#xff0c;当天可进行两次买卖#xff0c;故每天买卖有四种状态#xff0c;四种状态包含了当天不买不卖的状态。
…LeetCode:123.买卖股票的最佳时机III
123. 买卖股票的最佳时机 III - 力扣LeetCode
1.思路
将两次买入卖出转化为是否持有的状态当天可进行两次买卖故每天买卖有四种状态四种状态包含了当天不买不卖的状态。
2.代码实现 1class Solution {2 public int maxProfit(int[] prices) {34 // 根据买入卖出定义多种状态0表示不操作1表示第一次持有2表示第一次不持有3表示第二次持有4表示第2次不持有5 int[][] dp new int[prices.length][5];6 dp[0][0] 0;7 dp[0][1] -prices[0];8 dp[0][2] 0;9 dp[0][3] -prices[0];
10 dp[0][4] 0;
11
12 for (int i 1; i prices.length; i) {
13 // 第一次持有前一天就持有 或 第i天买入持有
14 dp[i][1] Math.max(dp[i - 1][1], -prices[i]);
15 // 第一次不持有前一天不持有 或 第i天不持有
16 dp[i][2] Math.max(dp[i - 1][2], dp[i - 1][1] prices[i]);
17 // 第二次持有前一天第二次持有 或 前一天不持有第i天持有
18 dp[i][3] Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
19 // 第二次不持有前一天第二次不持有 或前一天第二次持有第i天卖出
20 dp[i][4] Math.max(dp[i - 1][4], dp[i - 1][3] prices[i]);
21 }
22 return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][4]);
23 }
24}
253.复杂度分析
时间复杂度O(n). 空间复杂度O(1).
LeetCode:188.买卖股票的最佳时机IV
188. 买卖股票的最佳时机 IV - 力扣LeetCode
1.思路
在上一题的基础上将第i天是否持有股票或不持有和第几次持有或不持有股票作为一个循环体进行i天每天k次的循环遍历最终输出结果即可。
2.代码实现 1class Solution {2 public int maxProfit(int k, int[] prices) {34 // 定义dp[][][] 数组[天数][交易次数][是否持有股票]5 int len prices.length;6 int[][][] dp new int[len][k 1][2];78 // 初始化dp数组9 // 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润
10 for (int i 0; i k; i) {
11 dp[0][i][1] -prices[0];
12 }
13
14 for (int i 1; i len; i) {
15 for (int j 1; j k; j) {
16 // 0 表示不持有股票
17 // 1 表示持有股票
18 dp[i][j][0] Math.max(dp[i - 1][j][0], dp[i - 1][j][1] prices[i]);
19 dp[i][j][1] Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
20 }
21 }
22 return dp[len - 1][k][0];
23 }
24}
253.复杂度分析
时间复杂度O(nk). 空间复杂度O(nk).
