Java 2ms solution with explanation


  • 0
    R

    How to improve our 4+ms solutions to 2ms?
    Nothing mysterious,we just need some pre-processing operation, convert the array to "Shorter Zigzag“ mode.
    Here's the code,nothing serious:

            int[] pr = new int[prices.length];
            boolean flag = false;
            int len = 0;
    
            for(int i = 0; i < prices.length - 1; i++)
                if((flag && prices[i] > prices[i + 1]) || (!flag && prices[i] < prices[i + 1])) {
                        pr[len++] = prices[i];
                        flag = !flag;
                    }
            
            if(flag) pr[len++] = prices[prices.length - 1];
    

    And a little trick to accelerate when k >= length / 2:

            if(k >= len >> 1) {
                int total = 0;
                for(int i = 0; i < len; i+=2)
                    total += pr[i + 1] - pr[i];
                return total;
            }
    

    Through upper steps, we can alleviate the load of core codes by 1. Shorter array means shorter run time; 2. the cost to check hold/sell-strategy will be just the half.
    So here's the core:

            int[] hold = new int[k + 1];
            int[] sell = new int[k + 1];
            Arrays.fill(hold, Integer.MIN_VALUE);
            
            for(int i = 0; i < len; i+=2)
                for(int j = k; j > 0; j--) {
                    if(hold[j] < sell[j - 1] - pr[i]) hold[j] = sell[j - 1] - pr[i];
                    if(sell[j] < hold[j] + pr[i + 1]) sell[j] = hold[j] + pr[i + 1];
                }
    
            return sell[k];
    

    Note that if() is better here than ?: or Math.max().
    More explanation about the thinking of core codes lies here and thx a lot:[https://discuss.leetcode.com/topic/5934/is-it-best-solution-with-o-n-o-1/60]


Log in to reply
 

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