给定一个数组 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,]
考察要点:
- 数组
- 动态规划
