Best Time to Buy and Sell Stock

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if(prices==null || prices.length==0){
            return 0;
        }
        
        int min = Integer.MAX_VALUE;
        int res = Integer.MIN_VALUE;
        for(int i=0;i<prices.length;i++){
            min = Math.min(prices[i],min);
            res = Math.max(res,prices[i]-min);
        }
        
        return res;
    }
}

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

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if(prices==null||prices.length==0){
            return 0;
        }
        int n= prices.length;
        int[][] f = new int[n+1][5+1];
        
        f[0][0]=0;
        
        for(int i=1;i<=n;i++){
            //手中无股票
            for(int j=1;j<=5;j+=2){
                //情况1:昨日卖出
                f[i][j] = Math.max(f[i][j],f[i-1][j]);
                //情况2:昨日持有+今日卖出收益
                if(j>1 && i>1){
                    f[i][j] = Math.max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]);
                }
            }
            
            //手中有股票
            for (int j = 2; j <= 2 * 2; j += 2) {
                // two option: sell or don‘t sell
                if (i > 1) {
                    //情况1：昨日持有+今日收益
                    f[i][j] = Math.max(f[i][j], f[i - 1][j] + (prices[i - 1] - prices[i - 2]));
                }
                if (j > 1) {
                    //情况2:昨日卖出
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1]);
                }
            }
        }
        
        int res = Integer.MIN_VALUE;
        for (int j = 1; j <= 5; j += 2) {
            res = Math.max(res, f[n][j]);
        }
        
        return res;
    }
}

public class Solution {
    /**
     * @param K: An integer
     * @param prices: An integer array
     * @return: Maximum profit
     */
    public int maxProfit(int K, int[] prices) {
        // write your code here
        int n = prices.length;
        if(n==0){
            return 0;
        }
        
        if(K>n/2){
            int tmp =0;
            for(int i=0;i<n-1;i++){
                tmp+=Math.max(0,prices[i+1]-prices[i]);
            }
            
            return tmp;
        }
        
        int[][]f = new int[n+1][2*K+1+1];
        
        f[0][0] = 0;
        for(int i=1;i<=n;i++){
            //不持有股票的情况
            for(int j=1;j<=2*K+1;j+=2){
                //昨日已卖出
                f[i][j] = Math.max(f[i][j],f[i-1][j]);
                if(i>=2 && j>1){  //注意要加入j>1的边界，j=1时，前一状态是不可能持有股票
                    //昨日持有，今日卖出
                    f[i][j] = Math.max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]);
                }
            }
            
            //持有股票
            for(int j =2;j<=2*K;j+=2){
                //昨日已持有，需累加今日收益
                if(i>=2)
                f[i][j] = Math.max(f[i][j],f[i-1][j]+prices[i-1]-prices[i-2]);
                //昨日不持有，今日刚买入
                f[i][j] = Math.max(f[i][j],f[i-1][j-1]);
            }
        }
        
        int res = 0;
        for(int j =1;j<=2*K+1;j+=2){
            res = Math.max(res,f[n][j]);
        }
        
        return res;
    }
}