# LeetCode 123. Best Time to Buy and Sell Stock III

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Do it DP front and back.

```public class Solution {
int[] pre;
int[] post;

public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;
pre = new int[prices.length];
post = new int[prices.length];

int min = prices;
for (int i = 1; i < prices.length; i++) {
if (prices[i] < min) min = prices[i];
pre[i] = prices[i] - min > pre[i-1] ? prices[i] - min : pre[i-1];
}
int max = prices[prices.length - 1];
for (int i = prices.length - 2; i >= 0; i--) {
if (prices[i] > max) max = prices[i];
post[i] = max - prices[i] > post[i+1] ? max - prices[i] : post[i+1];
}

int profit = 0;
for (int i = 0; i < prices.length; i++) {
int p = pre[i] + post[i];
if (p > profit) profit = p;
}
return profit;
}
}
```
Posted on Categories LeetCode, Tech