携手创造，一起生长！这是我参加「日新方案 8 月更文应战」的第30天，点击检查活动概况

前语

咱们社区陆续会将顾毅（Netflix 增加黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解收拾为文字版以方便咱们学习与阅览。

LeetCode 算法到目前咱们现已更新到 186 期，咱们会保持更新时刻和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，咱们期望咱们能够在上班路上阅览，持久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果咱们有建议和定见欢迎在文末留言，咱们会尽力满意咱们的需求。

难度水平：困难

1. 描述

给定一个整数数组prices ，它的第 i 个元素prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来核算你所能获取的最大赢利。你最多能够完成 k 笔买卖。

留意： 你不能同时参加多笔买卖（你必须在再次购买前出售掉之前的股票）。

2. 示例

示例 1

输入：k = 2, prices = [2,4,1]
输出：2
解说：在第 1 天 (股票价格 = 2) 的时分买入，在第 2 天 (股票价格 = 4) 的时分卖出，这笔买卖所能取得赢利 = 4-2 = 2 。

示例 2

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解说：在第 2 天 (股票价格 = 2) 的时分买入，在第 3 天 (股票价格 = 6) 的时分卖出, 这笔买卖所能取得赢利 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时分买入，在第 6 天 (股票价格 = 3) 的时分卖出, 这笔买卖所能取得赢利 = 3-0 = 3 。

提示：

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

3. 答案

class BestTimeBuySellStockIV {
    func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
        let n = prices.count
        guard k > 0 && n > 1 else {
            return 0
        }
        guard k < n else {
            return makeMaxProfit(prices)
        }
        // local[i] means the maxProfit when sell happens at ith day
        var local = Array(repeating: 0, count: k + 1)
        // global[i] means the maxProfit at ith day
        var global = Array(repeating: 0, count: k + 1)
        for i in 0..<n - 1 {
            let diff = prices[i + 1] - prices[i]
            for j in stride(from: k, to: 0, by: -1) {
                local[j] = max(global[j - 1] + max(diff, 0), local[j] + diff)
                global[j] = max(global[j], local[j])
            }
        }
        return global[k]
    }
    private func makeMaxProfit(_ prices: [Int]) -> Int {
        var sum = 0
        for i in 1..<prices.count {
            let diff = prices[i] - prices[i - 1]
            sum += diff > 0 ? diff : 0
        }
        return sum
    }
}
  • 首要思想：动态规划，最佳买入时机卖出股票的通解III，做一个全局和局部的动态数组，找出最大的值。
  • 时刻复杂度： O(n^2)
  • 空间复杂度： O(n)

留意: 当 k >= n 时，动态规划效率不高，咱们能够利用 Best Time Buy – Sell Stock II 中的方法

该算法题解的仓库：LeetCode-Swift

点击前往 LeetCode 操练

关于咱们

咱们是由 Swift 爱好者一起保护，咱们会共享以 Swift 实战、SwiftUI、Swift 基础为中心的技术内容，也收拾收集优秀的学习资料。