Buying and Selling stocks with maximum profit | Hacker News Reader

Buying and Selling stocks with maximum profit

codingismycraft.com

Commenters should note the constraint in the problem definition that the maximum number of buy-sell pairs allowed is two.

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.

The 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."

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

The page claims

>[7, 3, 13, 13, 6, 19, 10, 8, 15, 18]

>the maximum profit that can be made is 26 which is made as

>follows:

>Buy at 3 – Sell at 19, Buy at 8 – Sell at 18

However wouldn't profit be maximized with

B3, S13, B6, S19, B8, S18 for a total of profit of 33?

The problem states that the maximum number of transactions are two: We are given a list of integers representing stock prices; we must find the maximum profit that can be made assuming at most two no overlapping BUY – SELL transactions.

Apologies, thanks for clarifying.

There is a small typo which I think caused me some trouble parsing the sentence. In hindsight however the problem definition seems clear.

Reply on news.ycombinator.com