LeetCode 股票问题

今天起来看小红书，发现有人在那里寻死觅活，一看好像是以太坊价格波动，导致一群人又没过好年，发出微信里面说什么不想和妈妈说自己亏了多少多少的截图。不懂这些东西，只是觉得要是真实的股票问题能有算法题里面那么容易就好了，先总结一下目前刷到过的股票问题好了

买卖股票的最佳时机

只能买卖一次，记录一下到目前为止的最小值，然后遍历一遍数组，更新最大利润即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func maxProfit(prices []int) int {
    if len(prices) < 2{
        return 0
    }
    minPrice, maxProfit := prices[0], 0
    for i := 1; i < len(prices); i ++ {
        minPrice = min(minPrice, prices[i])
        maxProfit = max(maxProfit, prices[i] - minPrice)
    }
    return maxProfit
}

当然，这题的思想我感觉很类似另一个叫做 Kadane’s Algorithm 的算法，可以用来解决最大子数组和的问题，其实都是贪心的方法

1
2
3
4
5
6
7
8


func maxSubArray(nums []int) int {
    maxSum, currentSum := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        currentSum = max(nums[i], currentSum + nums[i])
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}

买卖股票的最佳时机 II

能买无数次，那这里就变成了最简单的动态规划，维护两个行为的最大收益，一个是wait一个是hold，然后遍历一遍数组，更新这两个状态即可

1
2
3
4
5
6
7


func maxProfit(prices []int) int {
    wait, hold := 0, math.MinInt32
    for i := 0; i < len(prices); i ++{
        wait, hold = max(wait, hold+prices[i]), max(hold, wait-prices[i])
    }
    return wait
}

买卖股票的最佳时机 III

能买两次，当然这里其实也是可以用动态规划来做的，但是我们其实可以两次贪心做出来，一次遍历第一次的收益，第二次反向遍历两次总共的收益，取最大就行

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func maxProfit(prices []int) int {
    if len(prices) < 2{
        return 0
    }
    n := len(prices)
    earn := make([]int, n)
    minP, maxP := math.MaxInt32, math.MinInt32
    res := 0
    for i := 0; i < n; i++{
        minP = min(minP, prices[i])
        if i > 0 {
            earn[i] = max(earn[i-1], prices[i]-minP)
        }
    }
    for i := n-1; i >= 0; i--{
        maxP = max(maxP, prices[i])
        if i+1 < n{
            earn[i] = max(earn[i+1], earn[i]+maxP-prices[i])
        }
        res = max(res, earn[i])
    }
    return res
}

买卖股票的最佳时机 IV

能买 k 次，这里就只能用动态规划了，相比较于二，买入和卖出分别维护一个长度为K的数组，然后遍历一遍数组，更新这两个数组即可

这里要注意下面几个容易错的事情

buy[i] 表示第i次买入的最大收益，初始化的时候是不可得状态，因此用最小值标注
为了方便起见我们把buy[0]和sell[0]看作边界，遍历的时候从1到k
遍历的时候不要使用未来数据，第i天的情况只和第i-1天的情况有关，因此要外层循环遍历日期，内层循环遍历购买次数，不过这个事情我其实没太明白

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n < 2{
        return 0
    }
    buy := make([]int, k+1)
    sell := make([]int, k+1)
    for i := 0; i <= k; i++{
        buy[i] = math.MinInt32
    }

    for i := 0; i < n; i++{
        for j := 1; j <= k; j++{
            buy[j] = max(buy[j], sell[j-1]-prices[i])
            sell[j] = max(sell[j], buy[j]+prices[i])
        }
    }
    res := 0
    for i := 1; i <= k; i++{
        res = max(res, sell[i])
    }
    return res
}