3ms Java DP solution beats 96.3%. O(kn) time; O(n) space.


  • 0
    A
    public class Solution {
        public int maxProfit(int k, int[] prices) {
            if(k == 0) return 0;
            int len = prices.length;
            
            if(k >= len/2) {
                int maxPro = 0;
                for(int i=1; i < len; i++)
                    if(prices[i] > prices[i-1])
                        maxPro += prices[i] - prices[i-1];
                return maxPro;
            }
            
            int[] dp = new int[2*k];
            for(int i=0; i < k; i++) {
                dp[i*2] = Integer.MIN_VALUE;
                dp[2*i+1] = 0;
            }
            
            for(int price : prices) {
                if(dp[0] < -price) dp[0] = -price;
                int sign = 1;
                
                for(int i=1; i < 2*k; i++) {
                    int tmp = dp[i-1] + sign*price;
                    if(dp[i] < tmp) dp[i] = tmp;
                    sign *= -1;
                }
            }
            
            return dp[2*k-1];
        }
    }

Log in to reply
 

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