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).

**Understand the problem:**

The problem is an extension to the previous question. The mainly difference is you can complete two transactions at most. So the logic is like:

- 0 transactions
- 1 transactions: buy -> sell
- 2 transactions: buy -> sell -> buy -> sell

**Naive Solution:**

We can divide the array into two halves, and calculate the maximal profit with only one transaction at each half. So the overall time complexity would be O(n^2).

**DP Solution:**

We can define two DP arrays. The first DP array, called left[n] denotes the maximal profit from 0 to i, where as the second DP array, called right[n] denotes the maximal profits from n -1 to i. So the maximal profit is to add them up.

**Code (Java):**

public class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int[] left = new int[prices.length]; int[] right = new int[prices.length]; process(prices, left, right); int maxProfit = 0; for (int i = 0; i < prices.length; i++) { maxProfit = Math.max(maxProfit, left[i] + right[i]); } return maxProfit; } private void process(int[] prices, int[] left, int[] right) { // find out the maximal profit from 0 to i int min = prices[0]; for (int i = 1; i < prices.length; i++) { left[i] = Math.max(left[i - 1], prices[i] - min); min = Math.min(min, prices[i]); } // Find out the maximal profit from n - 1 to i int max = prices[prices.length -1]; for (int i = prices.length - 2; i >= 0; i--) { right[i] = Math.max(right[i + 1], max - prices[i]); max = Math.max(max, prices[i]); } } }

**Updates on 10/13/14:**

Since the question asks for at most two transactions. For day i, we can get the maximal profit from [0, i], and the maximal profit from [i, end]. Finding the maximal profit from day [0, i] is relative easier to understand. Use a dp_left[i] stands for maximal profit from day 0 to day i. Getting the best profit from profit from day [i, end] is a bit trickier. If we still scan in forward order, for each element i, we need to scan all its following elements, so the complexity would be O(n ^ 2). If we scan from end in backward order, we need to only scan the array once. Then the maximal profit is the maximal sum of the two arrays given a day.

## No comments:

## Post a Comment