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

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

first thought is to use binary search, for each i:

  • find the maximal profit between [0..i]
  • find the maximal profit between [i+1..n]
  • then find the maximal sum for i postion.

This approach require O(n^2)

second approach is to do it in two pass:

  • first find all maximal profit between [0..i], where i reach to n. in this process, you need to keep track of the mininal buy-in price. if i sell at price[i] what is the maximal profit.
  • second find all maximal profit between[n..0] i.e. from the end to the begin. if I buy-in at price[i], what will be the maximal profit,, in this process, you need to keep the maximal sell price .

Related issue

public class Solution {
    public int maxProfit(int[] prices) {

        int res = 0;
        if(prices == null || prices.length <=1) return res;

        int[] p = new int[prices.length];

        int minBuyInPrice= prices[0];
        p[0] = 0;
        for(int i=1; i<p.length; i++){
            minBuyInPrice = Math.min(prices[i], minBuyInPrice);
            p[i] = Math.max(prices[i] - minBuyInPrice, p[i-1]);


        int[] q = new int[prices.length];
        q[q.length-1] = 0;
        int maxSellOutPrice = prices[q.length-1];
        for(int i= q.length-2; i>=0; i--){
            maxSellOutPrice = Math.max(prices[i], maxSellOutPrice);
            q[i] = Math.max(q[i+1], maxSellOutPrice- prices[i]);

        for(int i=0; i<q.length; i++){
            res = Math.max(res, q[i] + p[i]);

        return res;

results matching ""

    No results matching ""