制作一个景点介绍的网站html,无法分享到微信wordpress,手机网站上线左右滑动,多语言网站开发121 Best Time to Buy and Sell Stock (买卖股票的最佳时机)
你好#xff0c;2024年的第一个月#xff0c;又是秋风萧瑟天气凉#xff0c;草木摇落露为霜。.。。在这个特殊的时代#xff0c;作为我们普通的一个打工人#xff0c;我们用这道题#xff0c;开启对这个不符合…121 Best Time to Buy and Sell Stock (买卖股票的最佳时机)
你好2024年的第一个月又是秋风萧瑟天气凉草木摇落露为霜。.。。在这个特殊的时代作为我们普通的一个打工人我们用这道题开启对这个不符合经济增长规律的股市反抗一把。
题目描述
有这样一个数组 prices 其中 prices[i] 是给定股票在 ith天的价格。
我希望通过选择某一天购买一只股票并选择未来的另一天出售该股票来最大化的利润。
返回从本次交易中获得的最大利润。如果你无法获得任何利润返回 0 。 这里我个人小白理解分析
这道题我上来一看就感觉股市要是能预测成这样那大家不全都赚到钱了有些扯。但谁叫面试官喜欢这道题呢那我还是继续看题吧毕竟万一通过刷明白这道题有钱请白月光吃麻辣烫了呢。 这里我们那这个数组来进行理解 [7,1,5,3,6,4]
7 是我们看到的最便宜的开始价格我们是无法在第一天出售因此 maxProfit 为 0
1 现在是我们见过的最便宜的价格。现在出售会我们肯定就亏了所以我们无法更新 maxProfit
5 比1贵但如果我们现在出售我们得到的最大利润为 4最好保存起来供以后使用
3 比1也贵如果我们出售我们只获得的利润为2那么我们不需要在这里做改变
6 是比1更贵但如果我们在这里出售我们会将 maxProfit 增加到 5使其成为最佳回报利润。
4 比1也贵如果我们出售我们只获得的利润为3比6的时候去卖获得的利润更少那么我们在这里也不做改变
解题过程
上来咱就是主打一个快别让面试官久等了。另外我还要去请白月光吃饭呢。
public static int maxProfit2(int[] prices){// 最大利润int maxProfit 0;// 遍历所有可能的买入和卖出时机for (int i 0; i prices.length; i) {for (int j i 1; j prices.length; j) {// 计算利润int profit prices[j] - prices[i];// 更新最大利润if (profit maxProfit) {maxProfit profit;}}}return maxProfit;}小明OK完事儿等着面试官来表扬自己吧。他肯定会说小子你是个好手工位都给你准备好了工资你说了算。
面试官嗯你这个要是nums2 给了十万个数是不是会影响性能
小明OS今年这个找工市场人言洛阳花似锦偏我来时不逢春。。。怎的技能要求突然涨了不是做出来就行
好吧逼我拿出压箱底的东西是吧。的确这个算法是偏慢。
话不多说拿动态方程说话
dp[i] max(dp[i - 1], prices[i] - min(prices[0:i]))
其中
dp[i] 表示在第 i 天卖出股票最大利润prices[i] 表示第 i 天的股票价格min(prices[0:i]) 表示第 0 天到第 i 天中最小的股票价格
小白的理解过程
动态方程的含义是在第 i 天卖出股票最大利润可以从以下两种情况中取最大值
在第 i - 1 天卖出股票最大利润 在第 i 天买入股票然后在第 i 天卖出股票利润为 prices[i] - min(prices[0:i])
public static int maxProfit(int[] prices) {// 最大利润int[] dp new int[prices.length];// 初始化dp[0] 0;// 计算 dp[i]for (int i 1; i prices.length; i) {// 计算在第 i 天卖出股票最大利润dp[i] Math.max(dp[i - 1], prices[i] - min(prices[0:i]));}// 返回最大利润return dp[prices.length - 1];}private static int min(int[] prices) {int minPrice prices[0];for (int price : prices) {if (price minPrice) {minPrice price;}}return minPrice;}终于看到了面试官满意的点头OK进入下一面 编码道路漫漫只要先看脚下的路徐徐前进即可。
