# Java 2ms solution with explanation

• 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];
}
``````

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]

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