赞
踩
Author: Once Day Date: 2024年4月22日
漫漫长路,才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候最多只能持有 一股 股票。你也可以先购买,然后在同一天出售。
返回你能获得的最大利润 。
例如对于prices = [7,1,5,3,6,4]
,最大利润为7,即:
这道题需要找出在给定股票价格数组 prices
中能获得的最大利润,其中 prices[i]
代表第 i
天的股票价格。规则是在任何一天,可以决定是否购买或者出售股票,但最多只能持有一股股票,并且允许在同一天买入和卖出。题目要求返回可能的最大利润。
关键在于理解在哪些天买入和在哪些天卖出可以获得最大利润。由于可以在同一天买入和卖出,那么只要今天的价格比昨天高,就可以认为昨天买入,今天卖出是有利可图的。
具体策略是:
这种策略的好处在于不需要维护任何复杂的状态,只需要在价格上升的时候“买卖”即可。
分析步骤:
maxProfit
来存储总利润,初值设为0。maxProfit
上。maxProfit
。性能优化关键点:
int maxProfit(int* prices, int pricesSize) { int32_t i, state, money, buy_price, last_price; state = 1; /* 买入 */ money = 0; last_price = buy_price = prices[0]; for (i = 1; i < pricesSize; i++) { if (prices[i] < last_price) { /* 降价卖出 */ if (state) { money += last_price - buy_price; state = 0; } } else if (prices[i] > last_price) { /* 升价买入 */ if (!state) { buy_price = last_price; state = 1; } } last_price = prices[i]; } /* 最后直接卖掉 */ if (state) { money += last_price - buy_price; } return money; }
这段代码实现了一个简单的股票交易策略,目标是最大化利润。函数的输入是一个整数数组 prices
,表示一段时间内股票的价格变化,数组的大小为 pricesSize
。
代码的主要逻辑如下:
初始化变量:state
表示当前的交易状态,1 表示持有股票(买入),0 表示不持有股票(卖出),money
表示当前的总利润,
buy_price
表示最近一次买入的价格,last_price
表示上一次的股票价格。
遍历价格数组,从下标 1 开始:
state
为 1),则卖出股票,计算利润并更新 money
,将 state
设为 0。state
为 0),则买入股票,将 buy_price
设为上一次的价格,将 state
设为 1。last_price
为当前价格。遍历结束后,如果仍持有股票(state
为 1),则以最后一个价格卖出,计算利润并更新 money
。
返回总利润 money
。
这个策略的核心思想是:在价格下降时卖出,在价格上升时买入,以期获得最大利润。
运行结果如下所示(仅供参考):
这个问题考察了对数组遍历和简单逻辑判断的应用,以及如何从实际问题中抽象出有效的解决方案。通过这种问题,可以加强对简单贪心算法的理解和应用。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。