力扣 初级算法 全套力扣精解

初级算法-动态规划-买卖股票的最佳时机

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. 在某一天买,在未来某一天卖 -> 只能买卖一次,不存在频繁买卖
  2. 最大利润 -> 找出买卖后最大的利润值即可
解决思路1:
  1. 根据分析1,说明需要买卖一次
  2. 根据分析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,]

考察要点:

上一篇下一篇

猜你喜欢

热点阅读