Skip to content

Instantly share code, notes, and snippets.

@PiotrJander

PiotrJander/mss_dyn_prog.hs

Created January 5, 2020 16:37
Show Gist options
  • Save PiotrJander/b6112dd3498a2dfec13798a4b5026bd7 to your computer and use it in GitHub Desktop.
Save PiotrJander/b6112dd3498a2dfec13798a4b5026bd7 to your computer and use it in GitHub Desktop.
Download ZIP
Lazy dynamic programming in Haskell
Raw
mss_dyn_prog.hs
maxSubsetSum :: [Int] -> Int
maxSubsetSum xs = maximum soln
where
len = length xs
arr = listArray (0, len - 1) xs
go 0 = 0
go 1 = 0 `max` (arr ! 0)
go n = (soln ! (n - 1)) `max` ((soln ! (n - 2)) + (arr ! (n - 1)))
soln = listArray (0, len) [ go i | i <- [0..len] ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment