3 ms·
Maybe I'm missing something, but none of the solutions given seem to offer optimal strategies, and the optimal solution appears to be pretty trivial. For exampl
by ajhurliman 6y ago
Maybe I'm missing something, but none of the solutions given seem to offer optimal strategies, and the optimal solution appears to be pretty trivial. For example, the first price list given is [7, 3, 13, 13, 6, 19, 10, 8, 15, 18], why not have buy/sell pairs at 3-13, 6-19, 8-18 for a total of 33 (better than the 26 which they offered as an optimal solution)?
You can get a O(n) solution by just looking ahead to the next price and buy at all the local minima and sell at all the local maxima.
- JackC 6y agoThe challenge is to make no more than two buy-sell transactions: "we must find the maximum profit that can be made assuming at most two no overlapping BUY – SELL transactions."
- ajhurliman 6y agoThe limitation of 2 buy-sell transactions and no overlapping buy-sell transactions are orthogonal. My solution listed 3 buy-sell transactions, but none of them are overlapping. Edit: I see now that it says "two no[sic] overlapping" trade pairs, which invalidates my solution.