算法练习之买卖股票的最佳时机

题目描述:

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

分析：买卖股票的最佳时机，也就是股票要买在低位，卖在高位，赚取差价，用数组表示一段时间内每天的股票价格，例如 [7, 10, 8, 3, 9]，第一天是7，第二天是10，第二天可以卖出，赚取差价3，8不可以买进，因为后面更低是3，3可以买进，9卖出，赚取差价6。整个过程下来，盈利为9。经过简单分析，我们可以得出结论：要保证每一次买卖都盈利，就要在prices[i] < prices[i + 1]的第i天买进，第i+1天卖出，prices[i] > prices[i + 1]的第i天不交易，这样盈利就达到多次卖出之后的(prices[i + 1] - prices[i])之和。

解答:

func maxProfit(_ prices: [Int]) -> Int {
    var income: Int = 0
    for i in 0 ..< prices.count - 1 {
        if prices[i] < prices[i + 1] {
            income += prices[i + 1] - prices[i]
        }
    }
    return income
}
maxProfit([7, 10, 8, 3, 9]) // 打印9