Discussion about this post

User's avatar
hfc's avatar

Thank you for sharing these nice solutions. However, it doesn't seem to give the correct result for the vector {1,2,3,4,5}. Both solutions give 4, but this is maximum profit with one transaction, not two. In the first solution, the suffix vector keeps track of the max(suffix[i+1], max - prices[i]) for each element i. But this would give the maximum profit achievable to the right, but including the current price, i.e [i..prices.size()). But in the description you say it should keep track of the maximum profit achievable to the right, but excluding the current price i, i.e. (i..prices.size()). Shouldn't the elements in the suffix vector be shifted by 1 to the left? So in this case suffix should be equal to [3, 2, 1, 0, 0] and not [4, 3, 2, 1, 0]. Also, since in the problem description it is stated that we want to find the maximum achievable profit with two transactions. But then we should not take into consideration the first and the last element in prices, since these will give the profits for a single transaction. In this case, I think the maximum achievable profit with two transactions is 3 via {buy:1, sell:3} + {buy:4, sell:5}.

Expand full comment
5 more comments...

No posts