給你一個整數(shù)數(shù)組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。
在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以先購買，然后在 同一天 出售。
返回 你能獲得的 最大 利潤 。

解題思路：動態(tài)規(guī)劃

(1) 定義dp數(shù)組
我們使用一維來定義天數(shù)，另一維定義狀態(tài)。（具體來說：是否持有股票）
● dp[i][0]：前 i 天（包括 i ）持有股票，獲取的最大利潤；
● dp[i][1]：前 i 天（包括 i ）沒有持有股票，獲取的最大利潤。

(2) 狀態(tài)轉移方程
當經過了 i - 1 天后，第 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])

? 區(qū)別于一次買賣！本題買賣可以進行多次，具體體現(xiàn)在持有股票上
● 一次買賣：如果買入第 i 天的股票，那么第i天持有股票的最大利潤，即dp[i][0]一定就是 -prices[i]；
● 多次買賣：所持有的現(xiàn)金可能有之前買賣過的利潤。如果買入第 i 天的股票，那么第i天持有股票的最大利潤，可能為 dp[i-1][1] - prices[i]，還要和dp[i-1][0]比較，看哪個利潤大；

(3) 初始化
● dp[0][0] = -prices[0]
● dp[0][1] = 0

(4) 遍歷順序
從前到后

(5) 舉例：略。

class Solution {
    public int maxProfit(int[] prices) {
        // dp[i][0]：前 i 天（包括第 i 天），持有股票 獲得的最大利潤
        // dp[i][1]：前 i 天（包括第 i 天），沒有持有股票 獲得的最大利潤
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1; i<prices.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        return dp[prices.length-1][1];
    }
}