Input: [7,1,5,3,6,4]
Output: 5
Explanation:
Buy on day 2 (price = 1) and sell on day 5 (price = 6),
profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than
buying price.
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Runtime: O(n) Space: O(1)
def maxProfit(prices: Array[Int]): Int = {
@tailrec
def go(i: Int, minSoFar: Int, profit: Int): Int = {
if (i == prices.length) profit
else {
go(
i + 1,
Math.min(minSoFar, prices(i)),
Math.max(prices(i) - minSoFar, profit)
)
}
}
prices.lift(0).fold(0)(go(1, _, 0))
}
Multiple Trades
A much more interesting problem, but alas I haven't found any practice sites or other forums where such a question was posited and an optimal solution detailed
NOTE: Implementation is still a work in progress as below devolves to O(n^2). But it's simple to reason about...Also a little bit of cheating using a while loop in terms of keeping things functional
def maxProfit(prices: Array[Int]): Int = {
@tailrec
def go(i: Int, sorted: Array[(Int, Int)], out: Int): Int = {
if (i == sorted.length) out
else {
var j = sorted.length - 1
while (j > i && sorted(j)._2 < sorted(i)._2) {
j -= 1
}
go(
if (j > i) i else i + 1,
if (j > i) sorted.patch(j, List.empty, 1).patch(i, List.empty, 1)
else sorted,
out + (sorted(j)._1 - sorted(i)._1)
)
}
}
go(0, prices.zipWithIndex.sorted, 0)
}