// Kvadraticke reseni
let rec ssum s = function
| [] -> None
| xs -> let partsums = List.scan (+) 0 xs
match List.tryFindIndex ((=)s) partsums with
| None -> ssum s xs.Tail
| Some i -> xs |> Seq.take i |> List.ofSeq |> Some
// O(N log N)
let ssum sum xs =
let sublist i len xs = xs |> Seq.skip i |> Seq.take len |> Seq.toList
let rec search i m = function
| [] -> None
| s :: ss -> let m' = Map.add s i m
match Map.tryFind (s - sum) m' with
| None -> search (i+1) m' ss
| Some j -> Some (sublist j (i-j) xs)
xs |> List.scan ((+)) 0
|> search 0 Map.empty