训练营第四十九天 | ● 121. 买卖股票的最佳时机 ● 122.买卖股票的最佳时机II

持有：第i-1天持有；第i天买入

不持有：第i-1天不持有；第i天卖出

代码随想录

class Solution {public int maxProfit(int[] prices) {//动态规划if(prices == null || prices.length == 0) return 0;int n = prices.length;int[][] dp = new int[n][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i-1][0], -prices[i]);//持有：第i-1天持有；第i天买入dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i]);//不持有：第i-1天不持有；第i天卖出}return dp[n-1][1];}
}

class Solution {public int maxProfit(int[] prices) {//动态规划滚动数组if(prices == null || prices.length == 0) return 0;int n = prices.length;int[][] dp = new int[2][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < n; i++) {dp[i%2][0] = Math.max(dp[(i-1)%2][0], -prices[i]);//持有：第i-1天持有；第i天买入dp[i%2][1] = Math.max(dp[(i-1)%2][1],dp[(i-1)%2][0] + prices[i]);//不持有：第i-1天不持有；第i天卖出}return dp[(n-1)%2][1];}
}

class Solution {public int maxProfit(int[] prices) {//动态规划滚动一维数组if(prices == null || prices.length == 0) return 0;int n = prices.length;int[] dp = new int[2];dp[0] = -prices[0];dp[1] = 0;for(int i = 1; i < n; i++) {dp[1] = Math.max(dp[1],dp[0] + prices[i]);//不持有：第i-1天不持有；第i天卖出dp[0] = Math.max(dp[0], -prices[i]);//持有：第i-1天持有；第i天买入//注意顺序不能颠倒，因为dp[1]包含前一天的dp[0]，若交换顺序，会更新当天的dp[0]，不能保证dp[1]的取值}return dp[1];}
}

class Solution {public int maxProfit(int[] prices) {//贪心,找到最左最小值，最右最大值int res = 0;int low = Integer.MAX_VALUE;for(int i = 0; i < prices.length; i++) {low = Math.min(low, prices[i]);res = Math.max(res, prices[i] - low);}return res;}
}

class Solution {public int maxProfit(int[] prices) {//暴力int res = 0;for(int i = 0; i < prices.length; i++) {for(int j = i + 1; j < prices.length; j++) {res = Math.max(res, prices[j] - prices[i]);}}return res;}
}

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

持有：第i-1天持有；第i天买入

不持有：第i-1天不持有；第i天卖出

与上题区别在于持有状态考虑买入时要加上前一天的不持有的钱数。即dp[0] = Math.max(dp[0], dp[1] - prices[i]);

代码随想录