2 ms Java DP solution beats 99.87%


  • 3
    Y

    The basic idea is similar to solution here: https://leetcode.com/discuss/75785/2ms-java-dp-solution

    I generalized it to K transactions.

    public class Solution {
        public int maxProfit(int k, int[] prices) {
            if (k <= 0 || prices == null || prices.length <= 0) return 0;
            if (k > prices.length / 2) { // in this case, it's the same problem as Best Time to Buy & Sell Stock II
                int max = 0;
                for (int i = 0; i < prices.length - 1; i++) {
                    int diff = prices[i + 1] - prices[i];
                    max += diff>0 ? diff : 0;
                }
                return max;
            } else {
                int [] buy = new int[k];
                int [] sell = new int[k];
                
                Arrays.fill(buy, Integer.MIN_VALUE);
                
                for (int price: prices) {
                    int tmp = 0;
                    for (int i = 0; i < k; i ++) {
                        int buffer = 0;                          // used to avoid duplicate calculation
                        buffer = tmp - price;
                        if (buy[i] < buffer) buy[i] = buffer;
                        
                        buffer = buy[i] + price;
                        if (sell[i] < buffer) sell[i] = buffer;
                        tmp = sell[i];
                    }
                }
                
                return sell[k - 1];
            }
            
        }
    }

  • 0
    M

    Nice one..only thing I could not understand is that upper part when k>prices.length/2. To be accurate I think we still have to maintain track of how many transaction are done..Please explain this.


  • 0
    W

    I believe this part is because with more than prices.length / 2 transactions, it is the same as no transactions limit since you can do only 1 transaction per 2 days. Then it becomes the same problem as Best Time to Buy & Sell Stock II.


  • 0
    B

    Just test it and got " Time Limit Exceeded " but run more times it do reach 2 ms . cool
    Mark for following readers .


Log in to reply
 

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