[Swift]LeetCode123.买卖股票的最佳时机III|BestTimetoBuyandSellStockIII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

24ms

  1 class Solution {
  2     func maxProfit(_ prices: [Int]) -> Int {
  3         
  4         if prices.count < 2 {
  5             return 0
  6         }
  7         
  8         //计算单次获利最大区间
  9         let receive = findMax(prices, 0, prices.count-1)
 10         
 11         //获利金额
 12         let profitFirst = receive.profit;
 13         
 14         //区间起始位置,将数组分成三部分,分别求第二次获利金额
 15         let startIndex = receive.startIndex;
 16         let endIndex = receive.endIndex;
 17         
 18         var subRange:[(start:Int, end:Int, isMid:Bool)] = []
 19         subRange.append((0, startIndex - 1, false));
 20         subRange.append((startIndex, endIndex, true));
 21         subRange.append((endIndex + 1, prices.count - 1, false));
 22         
 23         var profitSecond = 0
 24         
 25         for range in subRange {
 26             
 27             var tmpProfit = 0
 28             if range.isMid {
 29                 tmpProfit = -findMin(prices, range.start, range.end).profit
 30             } else {
 31                 tmpProfit = findMax(prices, range.start, range.end).profit
 32             }
 33             
 34             profitSecond = max(profitSecond, tmpProfit)
 35         }
 36         
 37         
 38         
 39         return profitFirst + profitSecond
 40     }
 41     
 42     
 43     func findMax(_ prices: [Int], _ startFlag: Int, _ endFlag: Int) -> (profit: Int, startIndex: Int, endIndex: Int) {
 44         
 45         if startFlag >= endFlag {
 46             return (0, 0, 0)
 47         }
 48         
 49         var startIndex = 0
 50         var endIndex = 0
 51         
 52         var tmpProfit = 0;
 53         var tmpStartIndex = startFlag;
 54         
 55         var total = 0
 56         
 57         for i in startFlag...endFlag {
 58             
 59             total = prices[i] - prices[tmpStartIndex]
 60             
 61             if total < 0 {
 62                 tmpStartIndex = i
 63                 total = 0
 64                 
 65             } else {
 66                 
 67                 if total > tmpProfit {
 68                     tmpProfit = total
 69                     endIndex = i
 70                     startIndex = tmpStartIndex
 71                 }
 72             }
 73         }
 74 
 75         return (tmpProfit, startIndex, endIndex)
 76     }
 77     
 78     func findMin(_ prices: [Int], _ startFlag: Int, _ endFlag: Int) -> (profit: Int, startIndex: Int, endIndex: Int) {
 79         
 80         if startFlag >= endFlag {
 81             return (0, 0, 0)
 82         }
 83         
 84         var startIndex = 0
 85         var endIndex = 0
 86         
 87         var tmpLoss = 0;
 88         var tmpStartIndex = startFlag;
 89         
 90         var total = 0
 91         
 92         for i in startFlag...endFlag {
 93             
 94             total = prices[i] - prices[tmpStartIndex]
 95             
 96             if total > 0 {
 97                 tmpStartIndex = i
 98                 total = 0
 99                 
100             } else {
101                 
102                 if total < tmpLoss {
103                     tmpLoss = total
104                     endIndex = i
105                     startIndex = tmpStartIndex
106                 }
107             }
108         }
109         
110         return (tmpLoss, startIndex, endIndex)
111     }
112 }

24ms

 1 class Solution {
 2     func maxProfit(_ prices: [Int]) -> Int {
 3         var maxPriceFromLeft = Array(repeating:0,count:prices.count)
 4         var minPrice = Int.max
 5         var delta = 0
 6         
 7         for (day,price) in prices.enumerated() {
 8             delta = max(price-minPrice,delta) 
 9             maxPriceFromLeft[day] = delta
10             minPrice = min(minPrice,price)
11         }
12 
13         var ans = 0
14         var maxPrice = 0
15         delta = 0
16         for index in stride(from:prices.count - 1,through:0,by:-1) {
17             delta = max(maxPrice - prices[index],delta)
18             ans = max(ans,maxPriceFromLeft[index] + delta)
19             maxPrice = max(maxPrice,prices[index])
20         }
21         
22         return ans
23     }
24 }

DP+状态机。

每个日期有6个整理状态：

1）零交易，不持有股票；

2）完成零交易，持有股票；

3）完成一笔交易，不持有股票；

4）完成一笔交易，持有股票；

5）两个交易完成，股票不持有；

6）两个交易完成，股票被持有。

这种模式可以推广到nt交易，我们可以使用二维数组来保持每个状态的最大利润，其中第一维是已完成交易的数量，第二维是持有股票与否。这个数组的大小是（NT + 1）* 2。

36ms

 1 class Solution {
 2     func maxProfit(_ prices: [Int]) -> Int {
 3         if prices.isEmpty {return 0}
 4         let nt = 2
 5         var profits = Array(repeating: [0, -prices[0]], count: nt + 1)
 6         
 7         for i in 0..<prices.count {
 8             profits[0][1] = max(profits[0][1], profits[0][0] - prices[i])
 9             for t in 1...nt {
10                 let temp = profits[t][0]
11                 profits[t][0] = max(profits[t][0], profits[t - 1][1] + prices[i])
12                 profits[t][1] = max(profits[t][1], profits[t][0] - prices[i])
13             }
14         }
15         print(profits)
16         return profits.max{$0[0] < $1[0]}![0]
17     }
18 }

52ms

 1 class Solution {
 2     func maxProfit(_ prices: [Int]) -> Int {
 3         guard prices.count > 0 else {
 4             return 0
 5         }
 6         
 7         var maxProfit = 0
 8         var finalMaxProfit = 0
 9         var maxProfitLeft = [Int]()
10         var low = prices.first!
11         var high = prices.last!
12         
13         for price in prices {
14             maxProfit = max(price - low, maxProfit)
15             low = min(price, low)
16             maxProfitLeft.append(maxProfit)
17         }
18         
19         maxProfit = 0
20         
21         for i in (0..<prices.count).reversed() {
22             let price = prices[i]
23             maxProfit = max(high - price, maxProfit)
24             high = max(price, high)
25             finalMaxProfit = max(finalMaxProfit, maxProfit + maxProfitLeft[i])
26         }
27         
28         return finalMaxProfit
29     }
30 }

104ms

 1 class Solution {
 2     func maxProfit(_ prices: [Int]) -> Int {
 3         guard prices.count > 1 else { return 0 }
 4         
 5         var curr = Array(repeating: 0, count: 3)
 6         var res = Array(repeating: 0, count: 3)
 7         for i in 0..<prices.count - 1 {
 8             for j in (1...2).reversed() {
 9                 var diff = prices[i + 1] - prices[i]
10                 curr[j] = max(res[j - 1] + (diff > 0 ? diff : 0), curr[j] + diff)
11                 res[j] = max(res[j], curr[j])
12             }
13         }
14         return res[2]
15     }
16 }