初级算法-动态规划-买卖股票的最佳时机
2021-09-08 本文已影响0人
coenen
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
摘一个示例做个说明.
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
条件分析:
- 在某一天买,在未来某一天卖 -> 只能买卖一次,不存在频繁买卖
- 最大利润 -> 找出买卖后最大的利润值即可
解决思路1:
- 根据分析1,说明需要买卖一次
- 根据分析2,可以找出每天买卖的收益进行对比
计算每天持有和不持有的收益,然后循环最大值,最后输出不持有时候的收益(因为需要卖出才能收益,所以最后肯定是不持有状态).
func maxProfit(_ prices: [Int]) -> Int {
if prices.count == 1 {
return 0
}
// 第一天不持有和持有的收益
var maxProfit0 = 0 ,maxProfit1 = -prices[0]
for i in 0 ..< prices.count {
// 第i天不持有和持有的收益
maxProfit0 = max(maxProfit0, maxProfit1 + prices[i])
maxProfit1 = max(maxProfit1, -prices[i])
}
// 最后需要卖出,所以是不持有
return maxProfit0
}
买卖股票的最佳时机提交结果.jpg
测试用例:
// 最小值
let nums = [0]
let nums = [1]
// 批量正常数据
let nums = [1,1,24,5,6,67,7]
let nums = [1,9,1,24,5,6,67,7]
let nums = [1,1,9,1,24,5,24,5,6,67,7]
let nums = [9,1,24,5,1,1,24,5,6,67,7]
let nums = [400,1,24,5,6,67,79,1,24,5,]
考察要点:
- 数组
- 动态规划