2
$\begingroup$

Question: Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice. The second buy has to come after first sell.

Solution: There is a O(N) time and O(N) space complexity solution, that keeps track of the maximum profit that can be made when selling at day i in a N size array. Then it calculates the max profit by using this array in conjunction with max profit that can be made by buying at day i+1.

I would appreciate any hints on how I can get a O(N) time and O(1) space complexity solution?

$\endgroup$
  • $\begingroup$ I was able to conceptualize the O(N), O(N) solution even without the help from the textbook but am totally stuck trying to figure how I can find the max profit without storing the the "one-time" maxProfits. I am not looking for a complete solution, just a hint. $\endgroup$ – Smart Home Jul 17 '16 at 6:26
  • $\begingroup$ This screams sweep-line algorithm. $\endgroup$ – Raphael Jul 17 '16 at 10:41
2
$\begingroup$

Hints:

The goal is to pick four values from the sequence such that

$$\frac{v_j}{v_i}\frac{v_l}{v_k}$$ is maximized. The solution is made of the two ratios that fulfill the order constraint while maximizing the product.

The best ratio in an interval is given by the maximum over the minimum, which you can find in time proportional to the interval size. You can also update the best ratio incrementally when you lengthen the interval, by recomputing the minimum and maximum.

If you sweep the whole array, you can obtain the best ratios on the left and right subarrays and compute their product. This is done in linear time on the left side (incrementally). So far, I have not found the trick to achieve linear time on the right (because the interval shrinks rather than lengthens).

$\endgroup$
  • $\begingroup$ Consider that you can only buy whole shares. If you have \$100, and share price goes from \$51 to \$60, you make only \$9 profit. If the share price goes from \$49 to \$55, you make \$12 profit because you can buy two shares, not just one. $\endgroup$ – gnasher729 Feb 15 at 0:05
  • $\begingroup$ @gnasher729: this remark is irrelevant to the working of my answer. You missed the point. $\endgroup$ – Yves Daoust Feb 15 at 7:59
1
$\begingroup$

At any point in time, you have either (a) not bought anything, (b) bought stock once, (c) bought and sold stock once, (d) bought and sold, then bought again, (e) bought and sold twice. In each case you have a certain amount of cash and a certain number of shares. Initially, you have all cash and zero shares in state (a); to simplify the algorithm assume that you might be in states (b) to (e) with a buy/sell of zero shares.

At each point when the share price is known, you could switch say from state (a) to (b), and you do that if the result is better than a previous state (b). Or switch from state (b) to (c) etc. You need only a fixed amount of memory for these five states, and O (n) comes from processing n new share prices.

$\endgroup$
  • $\begingroup$ This greedy approach does not work at all, it will immediately get stuck in a local maximum. $\endgroup$ – Yves Daoust Feb 14 at 8:51
  • $\begingroup$ If you say so, give an example. $\endgroup$ – gnasher729 Feb 15 at 0:00
  • $\begingroup$ Alternatively, argument why this should work at all. $\endgroup$ – Yves Daoust Feb 15 at 7:58
  • $\begingroup$ @YvesDaoust This answer clarifies how to apply dynamic programming. It is not greedy approach. $\endgroup$ – Apass.Jack Feb 15 at 15:34
  • $\begingroup$ @Apass.Jack: I don't see an ounce of dynamic programming here. Just a state machine. Your solution is barely drafted. $\endgroup$ – Yves Daoust Feb 15 at 15:37
1
$\begingroup$

Here's an O(1) space, O(n) time algorithm with Java code.

Logic:


Let $P_i$ denote the price of the stock on day $i$.

  • Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$.
  • If you had sold before day $i$ you can buy again at day $i$. If you do so, you'll need to deduct day $i$'s price from the 1st transaction's profit. Then, the maximum leftover profit at day $i$ is $Max(P_i - MaxProfit1_i)$. Call this $MaxLeftOver_i$.
  • In the same vein, if you had bought the 2nd stock before day $i$, you can sell it at day $i$. If you do so, you add day $i$'s price to the previous leftover profit to arrive at your profit at day $i$ with 2 transactions. Then, the maximum profit at day $i$ with 2 transactions is $Max(P_i + MaxLeftOver_i)$ - which is the final answer.
public int maxProfitWith2Transactions(int[] prices) {
    if (prices.length == 0) return 0;

    int minPrice                      = prices[0];
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int i = 1; i < prices.length; i++) {
        final int p = prices[i];
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell); 
        minPrice                    = Math.min(p, minPrice); 
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy); 
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell); 
    }
    return maxProfitAfterSecondSell;
}

The below modified (slightly faster) variant of the above beats every solution in both space and time on LeetCode.

public int maxProfitWith2Transactions(int[] prices) {
    int minPrice                      = Integer.MAX_VALUE;
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int p : prices) {
        minPrice                    = Math.min(p, minPrice); 
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell); 
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy); 
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell); 
    }
    return maxProfitAfterSecondSell;
}

Here's the values that the above code calculates for prices 8, 10, 3, 7, 4, 9, 2, 3. Clearly, the max profit after 1 transaction is 6 (Buy at 3, sell at 9). After 2 transactions, the max profit is 9 (Buy at 3, Sell at 7, Buy again at 4, sell at 9).

$$\begin{array}{l|r r r r r r r r} \text{$i$} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} \\ \hline \text{Price} & \text{8} & \text{10} & \text{3} & \text{7} & \text{4} & \text{9} & \text{2} & \text{3} \\ \\ \hline \text{Lowest price seen} & \text{8} & \text{8} & \text{3} & \text{3} & \text{3} & \text{3} & \text{2} & \text{2} \\ \text{till day $i$} \\ \hline \text{Max Profit if} & \text{x} & \text{2} & \text{2} & \text{4} & \text{4} & \text{6} & \text{6} & \text{6} \\ \text{bought at lowest} \\ \text{price before day $i$} \\ \text{and sold before} \\ \text{or on day $i$} \\ \hline \text{Max Profit left if} & \text{x} & \text{-8} & \text{-1} & \text{-1} & \text{0} & \text{0} & \text{4} & \text{4} \\ \text{2nd buy is done on} \\ \text{day $i$.} \\ \text{= Max(PreviousRow$_i$ - $P_i$)} \\ \hline \text{Max Profit if 2nd} & \text{x} & \text{2} & \text{2} & \text{6} & \text{6} & \text{9} & \text{9} & \text{9} \\ \text{stock is sold at} \\ \text{or before $P_i$} \\ \text{= Max(PreviousRow$_i$ + $P_i$)} \\ \hline \end{array}$$

$\endgroup$
  • $\begingroup$ Without explanation, simple code does not constitute answer here. $\endgroup$ – Evil Jul 20 at 8:58
  • 1
    $\begingroup$ @Evil, I've figured it out and put explanations. How about marking this as an asnwer? $\endgroup$ – eefiasfira Jul 21 at 1:00
-1
$\begingroup$
denote d[n] as array. index from 0 ~ e  where e = (n - 1)  
trans(i, j) = max(d[k2] - d[k1])  subject to:  k2 > k1 and k2 <= j  k1 >= i  
k1, k2 = argmax(trans(i, j))  k1 means buy point   k2 means sold point  
split(k) = trans(0, k) + trans(k+1, e)
we need to get max(split(k), subject to: 0 <= k <= e)

(1) caculate: i, j =  argmax(trans[0, e])
note the property:
     d[k] > d[i]  when k < i
     d[k] < d[j]  when k > j
     d[i] < d[k] < d[j] when i < k < j  

(2) easy to prove:
    split(k) <= split(i) when k <= i  
    split(k) <= split(j) when k >= j  
    caculate: trans(0, i-1) and trans(j+1, e)  

(3) caculate  split(k)  when  i < k < j  
   split(k) = trans(0, k) + trans(k+1, e)  
   consider:  
   trans(0, k) , A if sold before i,  trans(0, k) = trans(0, i-1)
                 B if sold after i, must buy  i  

   consider:
   trans(k+1, e), C if buy after j, trans(k+1, e) = trans(j+1, e)  
                  D if buy before j, must sold j  

   consider  all casees:
   split(k) = max( A + C, A + D, B + C, B + D)  
   A + C = tran(0, i - 1) + trans(j+1, e)  
   B + D,  a similary problem:   sold max and buy min between d[i+1] , d[j-1], will token o(n) time complexity  
   A  + D /  B + C   we   iterate on all possible k
$\endgroup$
  • $\begingroup$ Can you format your answer as text rather than as code? $\endgroup$ – Yuval Filmus Feb 14 at 11:21
  • $\begingroup$ Regarding your code, this is not a programming site, so I see no reason to include code here. For this reason, I have removed it. $\endgroup$ – Yuval Filmus Feb 14 at 11:57
  • $\begingroup$ it's ok to delete the code, the hints above is quite clear, i think~ $\endgroup$ – TAW8750 Feb 14 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.