Je bent consultant voor een investeringsbedrijf. De klant analyseert de waarde van een aandeel gedurende \(n\) opeenvolgende dagen in het verleden. Het is jouw taak om hem te adviseren op welk moment het aandeel het best aangekocht en vervolgens verkocht kon worden om de maximale winst te realiseren.
De dagen zijn genummerd als \(i = 0, 1, \ldots, n-1\). Voor elke dag \(i\) is er een aandelenprijs \(p(i)\), die gedurende de volledige dag constant blijft.
De bedoeling is om een koopdag \(i\) en een verkoopdag \(j\) te bepalen waarvoor \(j > i\) en waarvoor het verschil \(p(j) - p(i)\) maximaal is. Indien er binnen de gegeven periode geen winst mogelijk is (met andere woorden, als voor alle \(j > i\) geldt dat \(p(j) \leq p(i)\)), moet dit expliciet gerapporteerd worden.
Stel dat \(n = 3\) en \(p(0) = 9\), \(p(1) = 1\), \(p(2) = 5\). Het optimale advies is dan: aankopen op dag 1 en verkopen op dag 2. De winst bedraagt \(p(2) - p(1) = 5 - 1 = 4\) euro per aandeel, wat het maximum is binnen deze periode.
Een naïeve oplossing voor dit probleem vergelijkt alle mogelijke paren van koop- en verkoopdagen en heeft daardoor een tijdscomplexiteit van \(\Theta(n^2)\). Ontwerp een efficiënter verdeel-en-heersalgoritme met een tijdscomplexiteit van \(\Theta(n \log n)\) dat de beste koopdag \(i\) en verkoopdag \(j\) bepaalt.
Implementeer de interface Investment in een klasse MyInvestment. Voorzie een implementatie van de methode public BuySell bestInvestment(int[] values) die de optimale koop- en verkoopdag teruggeeft als een object van het recordtype BuySell. Indien geen winstgevende combinatie mogelijk is, moet de methode null teruggeven.
Gebruik de testklasse SimpleTest om je oplossing lokaal te testen. Je kunt hierin eenvoudig bijkomende testgevallen toevoegen.