121. 买卖股票的最佳时机

题意：

解题思路：

思路：
状态: dp[i][0]表示第i天不持有股票的最大收益，dp[i][1]表示第i天持有股票的最大收益。
状态转移方程:
1、前一天不持有股票; 或者前一天持有股票，今天卖出。取大的
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
2、前一天持有股票；或者前一天不持有股票，今天买入, 因为只能交易一次，今天买入了说明前一天没有买卖，所以今天的收益是-prices[i]。取大的
dp[i][1] = max(dp[i - 1][1], -prices[i]);
初始化:
dp[0][0] = 0;//还没开始，利润为0
dp[0][1] = -prices[0]; 
注意:
状态转移方程不是dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
初始化不能是最小值$dp[0][1] = PHP_INT_MIN，只能是买入花费的钱

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        if (count($prices) < 2) return 0;
        $maxProfit = 0;
        $buy = $prices[0];
        for ($i = 1; $i < count($prices); $i++) {
            if ($prices[$i] < $buy) {
                $buy = $prices[$i];
            } else {
                $maxProfit = max($maxProfit, $prices[$i] - $buy);
            }
        }
        return $maxProfit;
    }
    function maxProfitDp($prices) {
        if (empty($prices)) return 0;
        $dp = [];
        $dp[0][0] = 0;
        $dp[0][1] = -$prices[0];
        for ($i = 1; $i < count($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[count($prices) - 1][0];
    }
}

GO代码实现：

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    min, profit, n := prices[0], 0, len(prices)
    for i := 1; i < n; i++ {
        if prices[i] < min { 
            min = prices[i]
        } else if prices[i]-min > profit {   
            profit = prices[i]-min
        }
    }
    return profit
}