原题链接：

121. 买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

完成情况：

解题思路：

参考代码：

_121买卖股票的最佳时机_贪心递推

package 代码随想录.动态规划;public class _121买卖股票的最佳时机_贪心递推 {/**** @param prices* @return*/public int maxProfit(int[] prices) {//你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。//只能进行一次交易，即找出相对最小值，然后在后面找出对应的一个最大值int low = Integer.MAX_VALUE;//res不断更新，知道数组循环完毕int res = 0;for (int i = 0;i<prices.length;i++){low = Math.min(prices[i],low);res = Math.max(prices[i] - low,res );}return res;}
}

_121买卖股票的最佳时机_动态规划_01

package 代码随想录.动态规划;public class _121买卖股票的最佳时机_动态规划_01 {/**** @param prices* @return*/public int maxProfit(int[] prices){if (prices == null || prices.length == 0){return 0;}int len = prices.length;//dp[i][0]代表第i天持有的股票的最大收益//dp[i][1]代表第i天不持有股票的最大收益int dp [][] = new int[len][2];int result = 0;dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1;i<len;i++){dp[i][0] = Math.max(dp[i-1][0], -prices[i]);dp[i][1] = Math.max(dp[i-1][0]+prices[i],dp[i-1][1]);}return dp[len-1][1];}
}

_121买卖股票的最佳时机_动态规划_02

package 代码随想录.动态规划;public class _121买卖股票的最佳时机_动态规划_02 {/**** @param prices* @return*/public int maxProfit(int[] prices){int len = prices.length;int dp[][] = new int [2][2];dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1;i<len;i++){dp[i%2][0] = Math.max(dp[(i-1)%2][0], - prices[i]);dp[i%2][1] = Math.max(dp[(i-1)%2][1],prices[i]+dp[(i-1)%2][0]);}return dp[(len - 1) %2][1];}
}

_121买卖股票的最佳时机_动态规划_一维数组

package 代码随想录.动态规划;public class _121买卖股票的最佳时机_动态规划_一维数组 {/**** @param prices* @return*/public int maxProfit(int[] prices) {int[] dp = new int[2];// 记录一次交易，一次交易有买入卖出两种状态// 0代表持有，1代表卖出dp[0] = -prices[0];dp[1] = 0;// 可以参考斐波那契问题的优化方式// 我们从 i=1 开始遍历数组，一共有 prices.length 天，// 所以是 i<=prices.lengthfor (int i = 1; i <= prices.length; i++) {// 前一天持有；或当天买入dp[0] = Math.max(dp[0], -prices[i - 1]);// 如果 dp[0] 被更新，那么 dp[1] 肯定会被更新为正数的 dp[1]// 而不是 dp[0]+prices[i-1]==0 的0，// 所以这里使用会改变的dp[0]也是可以的// 当然 dp[1] 初始值为 0 ，被更新成 0 也没影响// 前一天卖出；或当天卖出, 当天要卖出，得前一天持有才行dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);}return dp[1];}
}

错误经验吸取