You have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

max_profit.purs

module Main where

import Prelude
import Control.MonadPlus (guard)
import Control.Monad.Eff.Console (logShow)
import Data.Array ((..), length, index)
import Data.List (List(..), (:), fromFoldable)
import Data.Tuple (Tuple, fst, snd)
import Data.Foldable (for_)
import Data.Maybe (fromMaybe)
import TryPureScript (render, withConsole)


main = render =<< withConsole do
  logShow $ run $ [1, 3, 8, 2, 4, 6, 10]
  logShow $ run $ []
  logShow $ run $ [5, 8, 6, 7, 6, 12]
  logShow $ run $ [5, 8, 1, 7, 6]


run :: Array Int -> Int
run arr = (bestInterval arr)


arrayToList :: Array Int -> List Int
arrayToList = fromFoldable


bestInterval :: Array Int -> Int
bestInterval arr =
  _bestInterval (arrayToList arr) 0 (fromMaybe 0 (index arr 0))
  where
    _bestInterval :: List Int -> Int -> Int -> Int
    _bestInterval Nil best bottom = best
    _bestInterval (Cons h hs) best bottom =
      if (h - bottom > best) then
        _bestInterval hs (h - bottom) bottom
      else
        if (h < bottom) then
          _bestInterval hs best h
        else _bestInterval hs best bottom