Space O(N) Time O(N*K) DP and Not Checking K > prcies.Length / 2 at all


  • 0
    L

    Performance hurts a little bit when executing the hardest test case which is because the way of length/2 using O(n) made it faster while this solution is calculating using dp which is O(n * k)

    public int MaxProfit(int k, int[] prices){
        int[] dp = new int[prices.Length];
        for(int i = 1, lastMax = 0; i <= k && i < prices.Length; i++){
            for(int j = 1, increase = int.MinValue, lastProfit = dp[0]; j < prices.Length; j++){
                int tmp = dp[j];
                increase = Math.Max(increase, lastProfit - prices[j - 1]);
                dp[j] = Math.Max(dp[j - 1], prices[j] + increase);
                lastProfit = tmp;
            }
            if(lastMax == dp[prices.Length - 1]) break;
            else lastMax = dp[prices.Length - 1];
        }
        return prices.Length == 0 ? 0 : dp[prices.Length - 1];
    }
    

    Below is the original solution with k compare with length/2.

    public int MaxProfit(int k, int[] prices){
        if(k >= prices.Length / 2){
            int result = 0;
            for(int i = 1; i < prices.Length; i++)
                result += prices[i] - prices[i - 1] <= 0 ? 0 : prices[i] - prices[i - 1];
            return result;
        }
        int[] dp = new int[prices.Length];
        for(int i = 1, lastMax = 0; i <= k; i++){
            for(int j = 1, increase = int.MinValue, lastProfit = dp[0]; j < prices.Length; j++){
                int tmp = dp[j];
                increase = Math.Max(increase, lastProfit - prices[j - 1]);
                dp[j] = Math.Max(dp[j - 1], prices[j] + increase);
                lastProfit = tmp;
            }
            if(lastMax == dp[prices.Length - 1]) break;
            else lastMax = dp[prices.Length - 1];
        }
        return dp[prices.Length - 1];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.