LeetCode刷题：121. 买卖股票的最佳时机（golang版）
package main
import "fmt"
func max(a int,b int) int {
if a>b {
return a
}
return b
}
//动态规划思想，核心有两点，1是每个步骤的状态定义，2是状态间的转换方程，首先要理清这两点
//本题为例，每天的状态有两个，持有股票或不持有股票，这里，0：代表不持有股票，可以理解为卖出，1：持有股票，可以理解为买入
//用dp[i][0]代表第i天不持有股票，dp[i][1]代表第i天持有股票
//首先分析dp[i][0]的情况可以由哪几个状态转换而来，两种情况，1：第i-1天卖出，第i天不操作,2：第i-1天买入，然后第i天卖出。所以，dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
//dp[i][1]类似，也是两种情况，1:第i-1天买入，第i天不操作，2：第i-1天卖出，然后第i天买入。所以，dp[i][1]=max(dp[i-1][1],-price[i]) 。注意这里情况2不能写成dp[i-1][1]-prices[i]，因为股票都是正数，最坏的情况应该是之前盈利为0，然后又买入了当天的股票，
func maxProfit(prices []int) int {
var dp = make(map[int]map[int]int)
dp[0] = map[int]int{0:0,1:-prices[0]}
for i:=1; i<len(prices); i++ {
sell := max(dp[i-1][0],dp[i-1][1]+prices[i])
buy := max(dp[i-1][1],-prices[i])
dp[i] = map[int]int{0:sell,1:buy}
}
return dp[len(prices)-1][0]
}
func main() {
p := []int{7,1,5,3,6,4}
res := maxProfit(p)
fmt.Println(res)
}