63. 股票的最大利润.md

解题思路

1. 动态规划

dp[i][0] 表示第 i 天持有股票的最少成本，可能是今天持有成本最小，也可能是之前持有成本最小 dp[i][1] 表示第 i 天不持有股票最大利润，可能是今天不持有利润最大，也可能是之前不持有利润最大

func maxProfit(p []int) int {
    if len(p) == 0 {
        return 0
    }
    // 初始化
    dp := make([][]int, len(p)+1)
    for i := range dp {
        dp[i] = make([]int, 2)
    }
    dp[1][0] = -p[0]
    dp[1][1] = 0
    for i := 2; i <= len(p); i++ {
        // 之前持有成本最小 or 今天持有成本最小
        dp[i][0] = max(dp[i-1][0], -p[i-1])
        // 之前不持有利润最大 or 今天不持有（今日价格-之前某天成本最小的价格）利润最大
        dp[i][1] = max(dp[i-1][1], dp[i][0] + p[i-1])
    }
    return dp[len(p)][1]
}

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

2. 优化动态规划

dp[i] 只和 dp[i-1] 有关，可以优化成单个变量 用 cost 记录前面遇到的最便宜股票 用 profit 记录当前最大利润

func maxProfit(p []int) int {
    profit := 0 // 利润
    cost := math.MinInt32  // 成本
    for i := range p {
        cost = max(cost, -p[i])
        profit = max(profit, cost + p[i])
    }
    return profit
}

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