**Problem:**

Say you have an array for which the *i*^{th} 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[0]; 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; } }

Comments are closed.