122. Best Time to Buy and Sell Stock II 发表于 2022-02-16 DP12345678910111213141516class Solution { public int maxProfit(int[] prices) { // 定义 dp[i][0] 为第 i 天休市且持有当日股票时的最大利润 // 定义 dp[i][1] 为第 i 天休市且未持有当日股票时的最大利润 int[][] dp = new int[prices.length][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[prices.length - 1][1]; // 最后一天休市时不持有股票利润最大 }} Greedy12345678910111213class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { // 第 i 天的股票价格高于第 i - 1 天,我们需要在第 i - 1 天买入股票 maxProfit += prices[i] - prices[i - 1]; } } return maxProfit; }} 可以理解为我们可以回到昨天,以今天的股票价格来决定昨天是否需要买入股票以使利润最大化。 Reference122. Best Time to Buy and Sell Stock II