代码随想录算法训练营|day48

121.买卖股票的最佳时机

本题中股票只能买卖一次
dp[i][0] 表示第i天不买入股票持有的最大现金；dp[i][1] 表示第i天买入股票持有的最大现金。

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	dp := make([][]int, len(prices))
	for i := 0; i < len(prices); i++ {
		dp[i] = make([]int, 2)
	}
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], -prices[i])
	}
	return dp[len(prices) - 1][0]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

空间优化：可以看到第i天状态只依赖于第i-1天的状态，因此只需要记录前一天状态即可

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	dp0, dp1 := 0, -prices[0]
	for i := 1; i < len(prices); i++ {
		dp0 = max(dp0, dp1+prices[i])
		dp1 = max(dp1, -prices[i])
	}
	return dp0
}
1
2
3
4
5
6
7
8
9
10
11

贪心：在历史最低点买入，最高点卖出

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	minPrice := prices[0]
	res := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] < minPrice {
			minPrice = prices[i]
		}
		res = max(res, prices[i]-minPrice)
	}
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

122.买卖股票的最佳时机II

较上题多了条件：股票可以进行多次买卖
dp[i][0] 表示第i天不买入股票持有的最大现金；dp[i][1] 表示第i天买入股票持有的最大现金。
所以在当天是买入状态时，持有的最大现金为前一天买入状态持有的最大现金和前一天卖出今天买入后持有的最大现金的最大值

func maxProfit(prices []int) int {
	if len(prices) == 0 || len(prices) == 1 {
		return 0
	}
	dp := make([][]int, len(prices))
	for i := 0; i < len(prices); i++ {
		dp[i] = make([]int, 2)
	}
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	}
	return dp[len(prices)-1][0]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

空间优化

func maxProfit(prices []int) int {
	if len(prices) == 0 || len(prices) == 1 {
		return 0
	}
	dp0, dp1 := 0, -prices[0]
	for i := 0; i < len(prices); i++ {
		dp0 = max(dp0, dp1+prices[i])
		dp1 = max(dp1, dp0-prices[i])
	}
	return dp0
}
1
2
3
4
5
6
7
8
9
10
11

贪心：只加正数
因为不限制交易次数，故只要今天股价比昨天高，就交易。

func maxProfit(prices []int) int {
	if len(prices) == 0 || len(prices) == 1 {
		return 0
	}
	sum := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			sum += prices[i] - prices[i-1]
		}
	}
	return sum
}

1
2
3
4
5
6
7
8
9
10
11
12
13

代码随想录文章详解

121.买卖股票的最佳时机
122.买卖股票的最佳时机II