本題之前采用貪心算法來解決，現在可以采用動態規劃來解決，通過dp數組記錄每次的狀態從而獲取到最大的利潤。

這里dp數組定義為二維數組 dp[price.length][2]，其中price.length表示第i天，[2]其中有0/1兩種狀態，[0]表示持有股票，[1]表示沒有持有股票。注意，持有并不代表一定是當天買入！也可能是之前買入的。

那么，dp[i][0]表示第i天持有股票，那么i-1天可能持有股票，此時是dp[i-1][0]，如果第i-1天沒有持有股票，那一定是第i天買入的，第i天買入股票，由于開始的時候手里沒有錢，當買入的時候，手里的金額是-price[i]。所以 持有股票的遞推公式dp[i][0] = Math.max(dp[i-1][0]，-price[i])。如果第i天不持有，就是dp[i][1] ，第i天不持有的話，可能是i-1天就不持有了，那么就是dp[i-1][1]，也可能是第i天賣掉了，那么就是dp[i-1][0]+price[i]。所以遞推公式就是dp[i][1] = Math.max(dp[i-1][1]，dp[i-1][0]+prices[i])。

初始化：dp[0][0]，表示第0天持有股票，那么一定是當天買入的股票，所以此時是-price[0]。dp[0][1]表示第0天不持有股票，則一定是0.

遍歷順序：我們是根據前一天的狀態得到后一天的狀態，所以i從1開始，直接遍歷。

打印數組

class Solution {public int maxProfit(int[] prices) {if (prices == null || prices.length == 0) return 0;int length = prices.length;// dp[i][0]代表第i天持有股票的最大收益// dp[i][1]代表第i天不持有股票的最大收益int[][] dp = new int[length][2];int result = 0;dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < length; i++) {dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);}return dp[length - 1][1];}
}