食品公司网站设计项目网络培训课程
LeetCode: 121. 买卖股票的最佳时机
121. 买卖股票的最佳时机 - 力扣（LeetCode）
1.思路
暴力解法、贪心也算比较符合思维，动规不容易想到，且状态处理不易处理
股票每天的状态为持有或不持有：声明dp数组：int[][] dp = new int[prices.length][2];
确定含义：dp[i][0] 表示第i天持有股票的最大收益，dp[i][1] 表示第i天不持有股票的最大收益。
初始化：dp[0][0] = -prices[0];dp[0][1] = 0;
2.代码实现
1// 动规2class Solution {3 public int maxProfit(int[] prices) {4 if (prices.length == 0 || prices == null) {5 return 0;6 }7 // dp[i][0] 表示第i天持有股票的最大收益8 // dp[i][1] 表示第i天不持有股票的最大收益9 int[][] dp = new int[prices.length][2];
10 dp[0][0] = -prices[0];
11 dp[0][1] = 0;
12 for (int i = 1; i < prices.length; i++) {
13 dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
14 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
15 }
16 return dp[prices.length - 1][1];
17 }
18}
19
1// 暴力解法2class Solution {3 public int maxProfit(int[] prices) {4 int profit = 0;5 for (int i = 0; i < prices.length; i++) {6 for (int j = i + 1; j < prices.length; j++) {7 profit = Math.max(profit, prices[j] - prices[i]);8 }9 }
10 return profit;
11 }
12}
13// 贪心算法
14class Solution {
15 public int maxProfit(int[] prices) {
16 int low = Integer.MAX_VALUE;
17 int res = 0;
18 for (int i = 0; i < prices.length; i++) {
19 low = Math.min(prices[i], low);
20 res = Math.max(prices[i] - low, res);
21 }
22 return res;
23 }
24}
3.时间复杂度
时间复杂度：O(n).
空间复杂度：O(1).
LeetCode: 122.买卖股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
1.思路
动规真香，可以一个套路解决多题
和上一题类似，每天股票有两种状态，持有或不持有。
递推公式：
第i天持有，有两种情况：①第i-1天就持有；②第i天买入持有；
第i天不持有，有两种情况：①第i-1天就不持有；②第i天卖出，说明第i-1天持有（包含了当天买入卖出）
2.代码实现
1class Solution {2 public int maxProfit(int[] prices) {3 if (prices.length == 0 || prices == null) {4 return 0;5 }6 int[][] dp = new int[prices.length][2];7 // 8 // 9 dp[0][0] = -prices[0];
10 dp[0][1] = 0;
11 for (int i = 1; i < prices.length; i++) {
12 // 第 i 天持有股票：①当天买入且前一天不持有；②前一天持有
13 dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
14 // 第 i 天不持有股票：①第 i 天卖出；②第i-1天就不持有
15 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
16 }
17 return dp[prices.length - 1][1];
18 }
19}
20
3.时间复杂度
时间复杂度：O(n).
空间复杂度：O(1).