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]