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.

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


  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) {
            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;

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s