Leetcode–Best Time to Buy and Sell Stock III

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

Notes:

  1. I used a brutal force way to call maxProfit (similar function as in Best Time to Buy and Sell Stock II) to get each of max profit of two halves. Then I realized actually if we store the max profit as array can avoid the duplicate recursive calls .
  2. As for the second half, similarly, go through prices backwards, to get an array of max profit of buying stock at day i and sell afterwards.

Java Solution

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<=1)
            return 0;
        //for first half
        int minP = prices[0];
        int maxP = prices[prices.length-1];
        int[] maxBefore = new int[prices.length];
        int[] maxAfter = new int[prices.length];

        int maxPro = 0;
        for(int i = 1; i<prices.length; i++){
            maxBefore[i] = Math.max(maxPro, prices[i]-minP);
            maxPro = maxBefore[i];
            minP = Math.min(minP, prices[i]);
        }
        maxPro = 0;
        for(int i = prices.length-2; i>=0; i--){
            maxAfter[i] = Math.max(maxPro, maxP - prices[i]);
            maxPro = maxAfter[i];
            maxP = Math.max(maxP, prices[i]);
        }
        // initialize using the single transaction case
        int profit = maxBefore[prices.length-1];
        // i is the beginning index of second transaction
        for(int i = 1; i < prices.length; i++){
            profit = Math.max(profit, maxBefore[i-1]+maxAfter[i]);
        }
        return profit;
    }   
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s