188. Best Time to Buy and Sell Stock IV

//O(nk) time and space
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(k>=n/2) return maxProfit2(prices);
        int[][] dp = new int[k+1][n];
        for(int i=1;i<=k;i++){
            int max = -prices[0];
            for(int j=1;j<n;j++){
                dp[i][j] = Math.max(dp[i][j-1], prices[j]+max);
                max = Math.max(max, dp[i-1][j-1]-prices[j]);
            }
        }
        return dp[k][n-1];
    }
    public int maxProfit2(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        int max = 0;
        for(int i=1;i<nums.length;i++){
            if(nums[i]-nums[i-1]>0) max+=(nums[i]-nums[i-1]);
        }
        return max;
    }
}


//O(n2k) time and O(nk)space
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(k>=n/2) return maxProfit2(prices);
        int[][] dp = new int[k+1][n];
        for(int i=1;i<=k;i++){
            for(int j=1;j<n;j++){
                int max = Integer.MIN_VALUE;
                for(int m=0;m<j;m++){
                    max = Math.max(max, prices[j]-prices[m]+dp[i-1][m]);
                }
                dp[i][j] = Math.max(max,dp[i][j-1]);
            }
        }
        return dp[k][n-1];
    }
    public int maxProfit2(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        int max = 0;
        for(int i=1;i<nums.length;i++){
            if(nums[i]-nums[i-1]>0) max+=(nums[i]-nums[i-1]);
        }
        return max;
    }
}