3 people like it.

# Maximum Sublist Problem

According to Wikipedia, the maximum sub-array problem is a programming task of finding the contiguous sub-array within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. The following is an attempt to solve this problem by using F# list rather than array.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: ``` ``````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 ``````
val split : lst:'a list -> 'a list * 'a list

Full name: Script.MaxSubList.split

Divide the input list into halves
val lst : 'a list
val mid : int
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val left : 'a list
module Seq

from Microsoft.FSharp.Collections
val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take
val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList
val right : 'a list
val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip
val collectState : lst:int list -> (int list * int) list

Full name: Script.MaxSubList.collectState

Collect states from mid towards the left end
val lst : int list
val scanBack : folder:('T -> 'State -> 'State) -> list:'T list -> state:'State -> 'State list

Full name: Microsoft.FSharp.Collections.List.scanBack
val x : int
val s : int list * int
val l : int list
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
val sum : list:'T list -> 'T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.List.sum
val maxList : lst:int list -> int list

Full name: Script.MaxSubList.maxList

Get the max state from the left list
val maxBy : projection:('T -> 'U) -> list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.maxBy
val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd
val collectState' : lst:int list -> (int list * int) list

Full name: Script.MaxSubList.collectState'

Collect states from mid towards the right end
val scan : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State list

Full name: Microsoft.FSharp.Collections.List.scan
val t : int
val maxList' : lst:int list -> int list

Full name: Script.MaxSubList.maxList'

Get the max state from the right list
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val crossMax : left:int list -> right:int list -> int list

Full name: Script.MaxSubList.crossMax

Crossing maximum subList
val left : int list
val right : int list
val maxLeft : int list
val maxRight : int list
val maxSubList : _arg1:int list -> int list

Full name: Script.MaxSubList.maxSubList

Recursive maxSubList
val leftMax : int list
val rightMax : int list
val crossingMax : int list
val sum : (int list -> int)
val testList1 : int list

Full name: Script.MaxSubList.testList1
val testList2 : int list

Full name: Script.MaxSubList.testList2