Skip to content

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

May 19, 2013

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.

To be continued…

Advertisements

From → F#

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: