module MaxSubList = /// Divide the input list into halves let split lst = let mid = (lst |> List.length)/2 let left = lst |> Seq.take mid |> Seq.toList let right = lst |> Seq.skip mid |> Seq.toList left, right /// Collect states from mid towards the left end let collectState lst = List.scanBack(fun x s -> let l = s|> fst x::l, (x::l |> List.sum)) lst ([],0) /// Get the max state from the left list let maxList lst = lst |> collectState |> List.maxBy snd |> fst /// Collect states from mid towards the right end let collectState' lst = List.scan(fun s t -> let l = s |> fst t::l, (t::l |> List.sum)) ([],0) lst /// Get the max state from the right list let maxList' lst = lst |> collectState' |> List.maxBy snd |> fst |> List.rev /// Crossing maximum subList let crossMax left right = let maxLeft = maxList left let maxRight = maxList' right maxLeft@maxRight /// Recursive maxSubList let rec maxSubList = function | [] -> [] | [x] -> [x] | lst -> let left, right = split lst let leftMax = maxSubList left let rightMax = maxSubList right let crossingMax = crossMax left right let sum = List.sum if sum leftMax >= sum rightMax && sum leftMax >= sum crossingMax then leftMax elif sum leftMax <= sum rightMax && sum crossingMax <= sum rightMax then rightMax else crossingMax // Testing cases let testList1 = [13;-3;-25;20;-3;-16;-23;18;20;-7;12;-5;-22;15;-4;7] let testList2 = [-2; 1; -3; 4; -1; 2; 1; -5; 4] // [18; 20; -7; 12] maxSubList testList1 // [4; -1; 2; 1] maxSubList testList2