Re: A Concise DP Solution in Java

In Problem III (At most two transaction), I try to understand and solve this problem from state machine perspective inspired by this amazing post: https://discuss.leetcode.com/topic/30680/share-my-dp-solution-by-state-machine-thinking

Then we conclude that we can use constant variable to represent 4 states and get a very concise solution as followed.

```
public int maxProfit(int[] prices) {
int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0;
for (int price : prices) {
buy1 = Math.max(buy1, -price);
sell1 = Math.max(sell1, buy1 + price);
buy2 = Math.max(buy2, sell1 - price);
sell2 = Math.max(sell2, buy2 + price);
}
return sell2;
}
```

Now for Problem IV, we can make at most K transaction rather than only two. Why not reuse the idea above? The only edge case is the first buy which has no previous sell. So here we create two int[k + 1] array to use sell[0] as a buffer region. Here is the solution.

```
public int maxProfit(int k, int[] prices) {
int[] buy = new int[k + 1], sell = new int[k + 1];
Arrays.fill(buy, Integer.MIN_VALUE);
for (int price : prices) {
for (int i = 1; i <= k; i++) {
buy[i] = Math.max(buy[i], sell[i - 1] - price);
sell[i] = Math.max(sell[i], buy[i] + price);
}
}
return sell[k];
}
```

Yes, that's all. While this will TLE for large test case, so it's necessary to add a special case handling to pass that. But don't be confused, the basic idea is only the piece of data above indeed.

```
if (k >= prices.length / 2) { // if k >= n/2, then you can make maximum number of transactions
int profit = 0;
for (int i = 1; i < prices.length; i++)
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;
}
```