Max Profit [2 variations: 1st Easy 2nd Hard]

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

One Trade

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)

}