最后更新于
最后更新于
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
示例 2:
其实就如同炒股票一样, 我们要找的其实就是波段的最低点和最高点, 他们之间的差就是利润, 找到最大的那一个.
我们知道小波段可以合成大波段, 反映的本题中, 就是对于一个区段低点, 从前向后遍历, 如果它之后出现过更低的点, 那么当前这个低点可能的最大利润对应的卖出高点, 一定在这个更低点之前, 否则在这个更低点买入利润更大. 因此从前向后遍历, 不断计算利润, 直到遇到更低的点, 更换到新的最低点后继续计算.
对于买卖股票这一系列的题目, 都可以考虑使用动态规划来做.
对于持有, 其实就是买入后的状态, 对应数组中的值一定是负的, 因此只有买入没有卖出. 持有分为之前买入和当天买入, 所以状态转移方程为:
其实就是在同上不停寻找最低点.
空仓状态同理, 分为之前也是空仓, 以及今天卖出导致空仓, 状态转移方程为:
本题要求股票只能买卖一次, 且股票状态只有持有和空仓两种, 因此可以创建两个数组, 分别记录对应状态第天所能获取的最大利润.
一直记录的都是当前时刻的最大利润.
考虑边界条件, 的值为, 持仓就需要买入嘛; . 最后的结果为.
状态转移方程只使用了天的结果, 可以使用滚动来节省空间.