题目Ⅰ
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
解法
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
min := prices[0]
max := 0
n := len(prices)
for i := 1; i < n; i++ {
pi := prices[i]
diff := pi - min
if diff > max {
max = diff
}
if pi < min {
min = pi
}
}
return max
}
遍历价格 prices，找出价格最底点，每次遍历时计算当前价格与最低点的差值，取最大值即可。
题目Ⅱ
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解法1：贪心算法
func maxProfit(prices []int) int {
flag := 0
n := len(prices)
for i := 1; i < n; i++ {
ppi := prices[i-1]
pi := prices[i]
if pi > ppi {
flag += pi - ppi
}
}
return flag
}
因为不限制交易次数，所以只要今天的价格比昨天高，就会有收益。
解法2：动态规划
func maxProfit(prices []int) int {
n := len(prices)
dp := make([][2]int, n)
dp[0][1] = -prices[0]
for i := 1; i < n; 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[n-1][0]
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
优化的动态规划：
func maxProfit(prices []int) int {
n := len(prices)
dp0, dp1 := 0, -prices[0]
for i := 1; i < n; i++ {
tdp0 := max(dp0, dp1+prices[i])
tdp1 := max(dp1, dp0-prices[i])
dp0 = tdp0
dp1 = tdp1
}
return dp0
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
题目Ⅲ
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解法：动态规划
func maxProfit(prices []int) int {
n := len(prices)
if n <= 1 {
return 0
}
dp := [3][2]int{}
dp[1][1] = -prices[0]
dp[2][1] = math.MinInt32
for i := 1; i < n; i++ {
dp[1][1] = max(dp[1][1], -prices[i])
dp[1][0] = max(dp[1][0], dp[1][1]+prices[i])
dp[2][1] = max(dp[2][1], dp[1][0]-prices[i])
dp[2][0] = max(dp[2][0], dp[2][1]+prices[i])
}
return max(dp[1][0], dp[2][0])
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
第一维表示交易次数，0：表示没有进行交易；1：表示已经买入1次股票；2：表示已经买入2次股票。
第二维表示是当前是否持股，0：表示当前不持股；1：表示当前持股。
优化的动态规划
func maxProfit(prices []int) int {
n := len(prices)
if n <= 1 {
return 0
}
dp10, dp11, dp20, dp21 := 0, -prices[0], 0, math.MinInt32
for i := 1; i < n; i++ {
var pi = prices[i]
dp11 = max(dp11, -pi)
dp10 = max(dp10, dp11+pi)
dp21 = max(dp21, dp10-pi)
dp20 = max(dp20, dp21+pi)
}
return max(dp10, dp20)
}
// max function
另外一种思路
func maxProfit(prices []int) int {
n := len(prices)
if n <= 1 {
return 0
}
/*
一维 表示天数
二维 五种状态
0: 初始状态
1: 第一次交易买入
2: 第一次交易卖出
3: 第二次交易买入
4: 第二次交易卖出
*/
dp := make([][5]int, n)
dp[0][1] = -prices[0]
dp[0][3] = math.MinInt32
for i := 1; i < n; i++ {
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
}
return max(dp[n-1][2], dp[n-1][4])
}
// max function
因为当前状态只和上一个状态有关，所以同样二维数组也可以使用变量代替。
题目Ⅳ
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解法1：动态规划
func maxProfit(k int, prices []int) int {
n := len(prices)
if n <= 1 {
return 0
}
if k >= n/2 {
// 此时交易次数已经不能影响最大收益, 按照不限次数处理
dp := make([][2]int, n)
dp[0][1] = -prices[0]
for i := 1; i < n; 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[n-1][0]
}
dp := make([][][2]int, n)
for i := range dp {
dp[i] = make([][2]int, k+1)
}
for i := 1; i <= k; i++ {
dp[0][i][1] = -prices[0]
}
for i := 1; i < n; i++ {
for j := 1; j <= k; j++ {
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])
}
}
return dp[n-1][k][0]
}
// max function
一维表示第几天，二维表示进行交易的次数，三维表示是否持有股票
状态转移方程：
T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k - 1][0] - prices[i])
优化的动态规划
因为当前状态只和上一个状态有关，所以可以优化数组，降低维数。
func maxProfit(k int, prices []int) int {
n := len(prices)
if n <= 1 {
return 0
}
if k >= n/2 {
// 此时交易次数已经不能影响最大收益, 按照不限次数处理
dp0, dp1 := 0, -prices[0]
for i := 1; i < n; i++ {
ddp0 := max(dp0, dp1+prices[i])
ddp1 := max(dp1, dp0-prices[i])
dp0, dp1 = ddp0, ddp1
}
return dp0
}
dp := make([][2]int, k+1)
for i := 1; i <= k; i++ {
dp[i][1] = -prices[0]
}
for i := 1; i < n; i++ {
for j := 1; j <= k; j++ {
dp[j][0] = max(dp[j][0], dp[j][1]+prices[i])
dp[j][1] = max(dp[j][1], dp[j-1][0]-prices[i])
}
}
return dp[k][0]
}
// max function
解法2：(未完成)
func maxProfit(k int, prices []int) int {
n := len(prices)
if n <= 1 {
return 0
}
// 递增区间和递减区间
up, down := make([]int, 0), make([]int, 0)
low, high := prices[0], -1
for i := 1; i < n; i++ {
if prices[i] > prices[i-1] {
if i+1 == n || prices[i+1] <= prices[i] {
up = append(up, prices[i]-low)
if high >= 0 {
down = append(down, high-low)
}
high = prices[i]
}
} else {
low = prices[i]
}
}
}
// TODO: 合并上升区间