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}.
Thank you for the clarification. But then I find the explanation of the solution a bit confusing, since you mention that we would like to compute max_profit(0,i)+max_profit(i+1,size()-1) for each index. But since the computation for the suffix includes the index i, it's not very intuitive to understand what is then being computed for each index i in the second iteration of the first solution. For example, in case of vector {1,2,3,4,5} we would get the sum of 2+2 for element 3, but this is not what is achievable with two transactions, since this would only be possible if you would buy and sell at the same price. But in the problem description it is stated that you can only do either a buy or sell at the same time. Would it be possible to clarify this?
I think you are misreading the formula. It's "i" and then "i+1" in the second part. So you cannot end up with 2 + 2, because that would max_profit(0,2) + max_profit(2,4). The actual formula is max_profit(0,2) + max_profit(3,4) == 2 + 1.
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}.
Indeed, and the maximum profit for {5,4,3,2,1} is 0, not -2.
The number of transactions is the available maximum, not a mandate.
Thank you for the clarification. But then I find the explanation of the solution a bit confusing, since you mention that we would like to compute max_profit(0,i)+max_profit(i+1,size()-1) for each index. But since the computation for the suffix includes the index i, it's not very intuitive to understand what is then being computed for each index i in the second iteration of the first solution. For example, in case of vector {1,2,3,4,5} we would get the sum of 2+2 for element 3, but this is not what is achievable with two transactions, since this would only be possible if you would buy and sell at the same price. But in the problem description it is stated that you can only do either a buy or sell at the same time. Would it be possible to clarify this?
I think you are misreading the formula. It's "i" and then "i+1" in the second part. So you cannot end up with 2 + 2, because that would max_profit(0,2) + max_profit(2,4). The actual formula is max_profit(0,2) + max_profit(3,4) == 2 + 1.
ah, you're right ^^'. My apologies for the confusion. Thank you!
ah, you're right ^^'. My apologies for the confusion. Thank you!