22/10/2017

[Java] Find local maximum gain in list

Here is another simple problem: given an ordered input of stock prices, find the best buy and sell times to achieve maximum gain.

The buy must happen before the sell and it is not possible to buy and sell in the same day. Return null if no gain can be achieved.

The idea is quite straightforward, in O(N) time and O(1) space, track the current maximum gain and current minimum buy date; whenever the gain can be increased, update the buy - if necessary - and store the sell data. Just as caution, it's important to remember to separately track the current and result data, otherwise it could be possible to wrongly overwrite the result before returning.

You can check on my Gist the implementation of the getMaxProfit (if only life was that easy..) method along with the test cases StockTradeJTests and the aux objects StockEntry and BuySellEntry.

No comments:

Post a Comment

With great power comes great responsibility