play-ocaml

committed 71122f6

Added solution to the maximum subarray problem

max_subarray/max_subarray.ml

`+(* Solves the maximum subarray problem using Kadane's algorithm. *)`
`+`
`+module Float = struct`
`+  let max (a : float) b = max a b`
`+end`
`+`
`+let kadane a =`
`+  let n = Array.length a in`
`+  let max_ending_here = ref 0. in`
`+  let max_so_far = ref 0. in`
`+  for i = 0 to n-1 do`
`+    max_ending_here := Float.max 0. !max_ending_here +. a.(i);`
`+    max_so_far := Float.max !max_so_far !max_ending_here`
`+  done;`
`+  !max_so_far`
`+`
`+let _ =`
`+  assert (kadane [|10.|] = 10. );`
`+  let test1 = [|-2.;-3.;4.;-1.;-2.;1.;5.;-3.|] in`
`+  assert (kadane test1 = 7.);`
`+  let test2 = [|-1.;1.;1.;-1.|] in`
`+  assert (kadane test2 = 2.)`
`+`
`+(* Note: Kadane's algorithm outputs zero when all numbers`
`+   are negative. However, in this case we simply compute`
`+   the maximum of the array to get the correct result. *)`
`+let _ =`
`+  let module Array = ArrayLabels in`
`+  let a = [|-4.;-8.;-.2.;-7.|] in`
`+  assert (kadane a = 0.);`
`+  let get_max = Array.fold_left ~init:neg_infinity ~f:Float.max in`
`+  assert (get_max a = -2.)`
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.