Skip to content

Instantly share code, notes, and snippets.

@rjeli

rjeli/profit.hs

Created November 8, 2015 07:34
Show Gist options
  • Save rjeli/60eff69b5176a1e07646 to your computer and use it in GitHub Desktop.
Save rjeli/60eff69b5176a1e07646 to your computer and use it in GitHub Desktop.
Download ZIP
Hardcore DP
Raw
profit.hs
profit :: [Int] -> Int
profit xs = f (head xs) 0 (tail xs)
where
f minVal maxDiff [] = maxDiff
f minVal maxDiff (x:xs) = f (min minVal x) (max maxDiff (x - minVal)) xs
-- O(n) time, O(1) memory
@rjeli
Copy link
Author

rjeli commented Nov 8, 2015

should be profit (x:xs) = f x 0 xs for better style points

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment