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

动态规划

考虑两个状态，天数和当天是否持有股票，不同状态下当天持有的最大现金：

当天持有股票：前一天持有并且当天不卖或者前一天没有当天买入。
当天没有持有股票：前一天没有持有并且当天不买或者前一天持有当天卖出。

最后一天不持有股票状态下的现金为最大值。

由于第n天的现金只与前一天的现金和是否持有股票有关，所以优化空间只用记录前一天持有和不持有股票的现金即可。

时间复杂度： O(N)
空间复杂度：O(1)

func maxProfit(prices []int) int {
    // dp[i][1] = max(dp[i-1][1], dp[i][0] - prices[i])
    // dp[i][0] = max(dp[i-1][0], dp[i][1] + prices[i])
    n := len(prices)

    dp := make([]int, 2)
    dp = []int{ 0, -prices[0] }

    for i := 1; i < n; i++ {
        temp0 := dp[0]
        dp[0] = max(dp[0], dp[1] + prices[i])
        dp[1] = max(dp[1], temp0 - prices[i])
    }

    return dp[0]

}

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