高端大气网络设计建设公司网站织梦模板,优秀网站网址,网站建设计算机人员招聘,90设计跟着carl学算法#xff0c;本系列博客仅做个人记录#xff0c;建议大家都去看carl本人的博客#xff0c;写的真的很好的#xff01; 代码随想录 LeetCode#xff1a;121.买卖股票的最佳时机1 给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票… 跟着carl学算法本系列博客仅做个人记录建议大家都去看carl本人的博客写的真的很好的 代码随想录 LeetCode121.买卖股票的最佳时机1 给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 示例 1 输入[7,1,5,3,6,4] 输出5 解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。 注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。 示例 2 输入prices [7,6,4,3,1] 输出0 解释在这种情况下, 没有交易完成, 所以最大利润为 0。 动态规划法
dp[i][0]表示第i天持有股票时的最多现金这里的持有并不是第i天买股票的意思也可以是第i - 1天买或第i - 2天买然后一直持有到第i天dp[i][1]表示第i天不持有股票时的最多现金初始化dp[0][0] -prices[0],dp[0][1] 0递推公式dp[i][0] Math.max(dp[i - 1][0], -prices[i]),dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i]) public int maxProfit(int[] prices) {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], -prices[i]);// 不持有股票要么昨天就不持有要么今天卖出dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i]);}// 肯定是不持有金额最多return dp[prices.length - 1][1];}贪心法
先找到第i天以前股票价格最低的时候然后在计算第i天卖出去所得到的利润 public int maxProfit(int[] prices) {int low Integer.MAX_VALUE;int res 0;for (int i 0; i prices.length; i) {low Math.min(low, prices[i]);res Math.max(res, prices[i] - low);}return res;}
