Wednesday, September 24, 2014

Leetocde: Best Time to Buy and Sell Stock III

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