杭州网站建设|网站设计,电子商务网站开发的基本原则,电子政务与网站建设方面,如何在网站做qq群链接Day42121. 买卖股票的最佳时机力扣题目链接给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返…Day42121. 买卖股票的最佳时机力扣题目链接给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。思路贪心算法遍历一遍数组计算每次 到当天为止 的最小股票价格和最大利润动态规划dp[i] [0] 表示第i天持有股票所得最多现金dp[i] [1] 表示第i天不持有股票所得最多现金最开始资金是0什么时候买了股票就扣除prices[i]第i天持有股票可能是i - 1就有股票也可能是之前没有资金为0第i天买入dp[i] [0] max(dp[i - 1] [0], -prices[i])第i天不持有股票可能是i - 1没有股票i没买也可能是i - 1有股票i卖出去了 dp[i] [1] max(dp[i - 1] [1], dp[i - 1] [0] prices[i])dp[0] [0] -prices[0], dp[0] [1] 0代码class Solution {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]);//记录到第i天的最低价格res Math.max(res,prices[i] - low);//同时可以计算出来到i天的最大利润}return res;}
}class Solution1 {public int maxProfit(int[] prices) {int[][] dp new int[prices.length][2];dp[0][0] -prices[0];//初始化dp数组dp[0][1] 0;for (int i 1; i prices.length; i){dp[i][0] Math.max(dp[i - 1][0], -prices[i]);//第i天有股票dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i]);//第i天没股票}return dp[prices.length - 1][1];}
}122.买卖股票的最佳时机II力扣题目链接给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。思路动态规划和上一题的区别是股票可以多次买入卖出因此在i时刻持有股票可能是i - 1就有股票i的时候没有卖也可能是i - 1的时候没有股票i的时候买入了什么是i - 1没有股票上一题是股票只能买一次这题是可以多次购买卖出因此没有股票的时候手里的钱不一定是0代码class Solution {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], 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];}
}
