# If Google would be looking to hire F# programmers – part 5

Next problem to be covered in this series is maximum subarray problem: the task of *finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum*.

An algorithm having **O(n)** complexity was first found by Jay Kadane. It scans through values computing at each position a maximum subarray ending in this position. This subarray is either empty having sum of elements equal to zero, or has one more element, than the same subarray ending in the previous position. Expressing this generically in F# is almost trivial with **Array.fold** combinator:

let inline kadanesV1 (xs: 'a []) = (LanguagePrimitives.GenericZero, LanguagePrimitives.GenericZero) |> Array.fold (fun (maxSum, maxSumEndingHere) x -> let maxSumEndingHere = (max LanguagePrimitives.GenericZero (maxSumEndingHere + x)) in ((max maxSum maxSumEndingHere), maxSumEndingHere)) <| xs |> fst

Folder function in line 4 maintains a maximum subarray, updating maximum sum in line 5. Here are some tests:

[| 1; -2; 1; -3; 4; -1; 2; 1; -5; 4 |] |> kadanesV1

val it : int = 6

[| 1.0; -2.0; 1.0; -3.0; 4.0; -1.0; 2.0; 1.0; -5.0; 4.0 |] |> kadanesV1

val it : float = 6.0

[| -1;-2;-3;0 |] |> kadanesV1

val it : int = 0

[| -1;-2;-3; |] |> kadanesV1

val it : int = 0

[| -3;-2;-1; |] |> kadanesV1

val it : int = 0

So far so good, but results of the last two test cases ask for a further generalization: how can we also correctly handle arrays consisting of just negative numbers? Comes out this requires trivial changes in lines 2 and 4:

let inline kadanesV2 (xs: 'a []) = (xs.[0], xs.[0]) |> Array.fold (fun (maxSum, maxSumEndingHere) x -> let maxSumEndingHere = if maxSumEndingHere < LanguagePrimitives.GenericZero then x else maxSumEndingHere + x in ((max maxSum maxSumEndingHere), maxSumEndingHere)) <| xs |> fst

Now we handle arrays of negative numbers too:

[| -1;-2;-3; |] |> kadanesV2

val it : int = -1

[| -3;-2;-1; |] |> kadanesV2

val it : int = -1

But what if we are also required to accompany the found largest sum with indices of subarray that constitutes it? This is where functional approach must seemingly get into trouble: so far we didn’t need dealing with any indices whatsoever, right?

Comes out we still would be able getting away with a folder. However, now we are forced to take care of much more moving parts, including the array element indices. This is where **Array.fold2** combinator comes to help:

let inline kadanesV3 (xs: 'a []) = ((xs.[0], 0, 0), (xs.[0], 0)) |> Array.fold2 (fun (maxSum, maxSumEndingHere) x i -> let maxSumEndingHere = let maxSumEndingHere, startIdxEndingHere = maxSumEndingHere if maxSumEndingHere < LanguagePrimitives.GenericZero then (x,i) else (maxSumEndingHere + x, startIdxEndingHere) in let maxSum = let maxSum, startIdx, endIdx = maxSum if maxSum < fst maxSumEndingHere then (fst maxSumEndingHere, snd maxSumEndingHere, i) else (maxSum, startIdx, endIdx) in (maxSum, maxSumEndingHere) ) <|| (xs,(xs |> Array.mapi (fun i _ -> i))) |> fst

Here in line #18 we arrange for folding the second array just consisting of indices of the first array, so our **Array.fold2** folder in line #3 is getting access to the current index, represented by lambda argument **i**. Although now we are taking care of significantly extended state we still can make folder **state** looking very similar to previous versions. However, now **maxSum** is 3-element tuple (line # 11) and **maxSumEndingHere** is 2-element tuple (line #5), carrying indices. Nevertheless, F# let bindings and shadowing allow us to fully localize these details within the folder, where these tuples are disassembled and reassembled at need.

Quick tests follow:

[| 1; -2; 1; -3; 4; -1; 2; 1; -5; 4 |] |> kadanesV3

val it : int * int * int = (6, 4, 7)

[| 1.0; -2.0; 1.0; -3.0; 4.0; -1.0; 2.0; 1.0; -5.0; 4.0 |] |> kadanesV3

val it : float * int * int = (6.0, 4, 7)

[| -1;-2;-3;0 |] |> kadanesV3

val it : int * int * int = (0, 3, 3)

[| -1;-2;-3; |] |> kadanesV3

val it : int * int * int = (-1, 0, 0)

[| -3;-2;-1; |] |> kadanesV3

val it : int * int * int = (-1, 2, 2)

Folding is a workhorse of functional programming, indeed.

## Trackbacks & Pingbacks