摘要：代碼解體思路依然是動態規劃，尋找狀態，因為本題涉及到，所以第天的狀態我們分為持股和未持股，即維護兩個數組，和分別表示第天持股和未持股所獲得的最大收益。

Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.

1.解題思路

想到用動態規劃，首先尋找狀態，dp[i] 表示第i天能獲得的最大收益，然后考慮狀態轉移，因為最多只允許1次股票交易，所以我們可以維護一個minPrice,對于dp[i],如果prices[i]比minPrice還要小，那么第i天肯定不應該賣出股票；如果prices[i]比minPrice大，我們就需要比較prices[i]-minPrice的收益和dp[i-1]的收益，以確定第i天要不要賣股票。

2.代碼

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int[] dp=new int[prices.length];
        int minPrice=prices[0];
        dp[0]=0;
        for(int i=1;i=minPrice){
                dp[i]=Math.max(dp[i-1],prices[i]-minPrice);
            }
            else{
                minPrice=prices[i];
                dp[i]=dp[i-1];
            }
        }
        return dp[prices.length-1];
    }
}

Best Time to Buy and Sell Stock II
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

1.解體思路

該題可以進行無數次股票交易，所以我們選擇貪心算法，即只要發現第i天價格比前一天高，就進行交易。遞增區間（1,4,5）就相當于昨天低價1塊買入，今天4塊賣出，收益3塊，再4塊買入，明天再5塊賣出，共收益3+1塊。

2.代碼

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int maxProfit=0;
        for (int i = 1; i < prices.length; i++) {
            maxProfit += prices[i] > prices[i-1] ? prices[i] - prices[i-1] : 0;
        }
        return maxProfit;
    }
}

Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.

1.解體思路
本題還是動態規劃，題目說最多進行2次交易，我們很容易就想到用left[i]和right[i]兩個數組來記錄狀態，
left[i]表示從0到i天獲得的最大收益，right[i]表示從i到最后一天獲得的最大收益，最后遍歷所有的left[i]和right[i]，使得left[i]+right[i]的和最大，即為題目的解。
分別分析left[i]和right[i].
1)left[i], 表示從0到i天獲得的最大收益, 其實和第一題一樣，借助minPrice;
2)right[i],表示從第i天買入開始的最大收益，相反，我們需要借助maxPrice,假設prices[i]比maxPrice小，那么通過比較right[i+1]和maxPrice-prices[i]來確定第i天是否要買入股票；如果prices[i]比maxPrice大，那么right[i]=right[i+1]維持不變，并更新maxPrice的值，以便進行下次比較。

2.代碼

public class Solution {
    public int maxProfit(int[] prices) {
        //at most two transactions means we can seperate the problem to left array & right array
        if(prices.length<2) return 0;
        int[] left=new int[prices.length];
        int[] right=new int[prices.length];
        //left side is the same as "Best Time to Buy and Sell Stock"
        int minPrice=prices[0];
        for(int i=1;i=minPrice){
                left[i]=Math.max(left[i-1],prices[i]-minPrice);
            }
            else{
                left[i]=left[i-1];
                minPrice=prices[i];
            }
        }
        //right side starts from the end of array.
        int maxPrice=prices[prices.length-1];
        for(int i=prices.length-2;i>=0;i--){
            if(prices[i]
Best Time to Buy and Sell Stock IV
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
1.解體思路
看到這題，我們就明白了其實前兩題II和III都是這一題的個例，II是允許有無數次的交易，即k>n/2,的情況，我們可以用貪心算法；而III其實就是k=2的情況。
我們需要維護兩個數組，globali表示到第i天發生j次交易所獲得的最大收益，locali表示到第i天發生j次交易，并且第j次交易發生在這一天所獲得的最大收益。
globali=Math.max(globali-1,locali);
globali-1表示第i天不發生交易，j次交易都在i天之前就已完成；
locali表示第j次交易發生在第i天。
locali=Math.max(globali-1+Math.max(0,prices[i]-prices[i-1]),locali-1+prices[i]-prices[i-1])
globali-1+Math.max(0,prices[i]-prices[i-1])表示在前i-1天的全局收益基礎上加上第i天可以得到的收益，如果prices[i]-prices[i-1]為負，則說明會虧損，所以我們就當作再i天又再次買入，所以收益不變；
locali-1+prices[i]-prices[i-1]:locali-1表示在第i-1天有進行第j次交易，現在我們把這次交易移到第i天。
2.代碼
public class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length<2) return 0;
        if(k+k>prices.length){
            int sum=0;
            for(int i=1;iprices[i-1]){
                    sum+=prices[i]-prices[i-1];
                }
                
            }
            return sum;
        }
        int[][] local_dp=new int[prices.length][k+1];
        int[][] global_dp=new int[prices.length][k+1];
        for(int i=1;i
Best Time to Buy and Sell Stock with Cooldown
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
1.解體思路
依然是動態規劃，尋找狀態，因為本題涉及到cooldown，所以第i天的狀態我們分為持股和未持股，即維護兩個數組，dp_hasstock[i]和dp_nostock[i]分別表示第i天持股和未持股所獲得的最大收益。
dp_nostock[i]=Math.max(dp_nostock[i-1],dp_hasstock[i-1]+prices[i]);
未持股分為兩種情況，一種是今天cooldown，所以就等于第i-1天賣出了股票后的最大收益；還有一種是今天賣股票，即前一天持股的最大收益加上今天賣出的股票價格：dp_hasstock[i-1]+prices[i]。
dp_hasstock[i]=Math.max(dp_nostock[i-2]-prices[i],dp_hasstock[i-1]);
持股也分為兩種情況，一種是昨天cooldown,今天買入股票，所以就等于前天賣出股票后的最大收益減去今天買入股票的價格；另一種情況繼續保持之前買入的股票，不進行交易。
2.代碼
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int[] dp_hasstock=new int[prices.length];
        int[] dp_nostock=new int[prices.length];
        dp_hasstock[0]=-prices[0];
        dp_nostock[0]=0;
        for(int i=1;i