esc to dismiss

123. 买卖股票的最佳时机 III

题目

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

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

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

示例 1:

输入:prices = [3,3,5,0,0,3,1,4]

输出:6

解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。

  随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3

示例 2:

输入:prices = [1,2,3,4,5]

输出:4

解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  

  注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。  

  因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入:prices = [7,6,4,3,1]

输出:0

解释:在这个情况下, 没有交易完成, 所以最大利润为 0

示例 4:

输入:prices = [1]

输出:0

解题思路

这道题开始我想的是跟 121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II 一样,用 差分 ,并在差分基础上加算法优化,结果代码写得很复杂,思路也稍微有些绕,且需要判断很多种边界条件,好不容易调试将所有用例都通过了。

代码:

func maxProfit(prices []int) int {
    size := len(prices) - 1
    diffs := make([]int, size, size)
    for i := 0; i < size; i++ {
        diffs[i] = prices[i+1] - prices[i]
    }

    sum := 0
    var sums []int
    sign, assigned := false, false // sign: true is positive
    for _, d := range diffs {
        if d == 0 {
            continue
        }

        if !assigned {
            // skip ahead negative sum
            if d < 0 {
                continue
            }
            sign = d > 0
            assigned = true
        }

        if sign == (d > 0) {
            sum += d
        } else {
            sums = append(sums, sum)
            sum = d
            sign = !sign
        }
    }

    // skip tail negative sum
    if sum > 0 {
        sums = append(sums, sum)
    }

    size = len(sums)
    if size == 0 {
        return 0
    } else if size == 1 {
        return sums[0]
    }

    order := make([]int, size, size)
    order[0] = sums[0]
    order[1] = order[0]
    for i := 2; i < size; i++ {
        if sums[i] > 0 {
            order[i] = max(sums[i], order[i-2]+sums[i-1]+sums[i])
        } else {
            order[i] = order[i-1]
        }
    }

    invert := make([]int, size, size)
    invert[size-1] = sums[size-1]
    invert[size-2] = invert[size-1]
    for i := size - 3; i >= 0; i-- {
        if sums[i] > 0 {
            invert[i] = max(sums[i], invert[i+2]+sums[i+1]+sums[i])
        } else {
            invert[i] = invert[i+1]
        }
    }

    maxSum := 0
    for i := size - 1; i >= 0; i-- {
        if maxSum > invert[i] {
            invert[i] = maxSum
        } else {
            maxSum = invert[i]
        }
    }

    profit := 0
    for i := 0; i < size-1; i++ {
        sum := order[i] + invert[i+1]
        if profit < sum {
            profit = sum
        }
    }
    return profit
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

后来看了题解,超级简单,用 动态规划

func maxProfit(prices []int) int {
    size := len(prices)
    buy1 := -prices[0]
    buy2 := -prices[0]
    sell1 := 0
    sell2 := 0
    for i := 1; i < size; i++ {
        buy1 = max(buy1, -prices[i])
        sell1 = max(sell1, buy1+prices[i])
        buy2 = max(buy2, sell1-prices[i])
        sell2 = max(sell2, buy2+prices[i])
    }
    return sell2
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

经验教训

略。

x