Maximum Subarray in Haskell
Dynamic programming is an algorithmic technique that trades space for improved runtime performance and takes advantage of overlapping subproblems. Memoization is a common strategy within Dynamic programming; store the results of expensive computations and look them up when the same input occurs again. Most literature on algorithms provide an imperative programming solution instead of a declarative one. I want to work through some dynamic programming problems with Haskell.
The maximum subarray problem is an easy place to start. Given a list of numbers, what is the subarray (contiguous) that sums to the largest value. If the array only includes positive values, then it is the entire subarray. If it includes negative values, then the answer is most likely a subarray. Kadane’s algorithm provides a solution in O(n) time. Here is the imperative form:
max_so_far = 0
max_ending_here = 0
For each element in the array a:
max_ending_here = max_ending_here + a[i]
if (max_ending_here < 0)
max_ending_here = 0
if (max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
The strategy is to store the max result of any subarray in max_so_far
and when the loop ends, it contains the correct answer. max_ending_here
contains the result from some index up to the current index. The beginning index of the subarray is reset if max_ending_here
is less than zero, and max_so_far
is updated only when it is less than max_ending_here
.
The translation to Haskell is pretty simple. Instead of two mutable values, we create an internal function that takes the updated values of maxSoFar
and maxEndingHere
and call it recursively over the values of the list and when the list is empty, we return the maxSoFar
value.
simpleMaxSubarray :: [Int] -> Int
simpleMaxSubarray = simpleMaxSubarray' 0 0
where
simpleMaxSubarray' maxSoFar maxEndingHere [] = maxSoFar
simpleMaxSubarray' maxSoFar maxEndingHere (x:xs) = simpleMaxSubarray' maxSoFar' maxEndingHere' xs
where
maxEndingHere' = max x (maxEndingHere + x)
maxSoFar' = max maxSoFar maxEndingHere'
I decided to improve the function and return the start and end indexes of the max subarray.
maxSubarray :: [Int] -> (Int, Int, Int)
maxSubarray = maxSubarray' 0 0 0 0 0
where
maxSubarray' maxSoFar maxEndingHere i start end [] = (maxSoFar, start, end)
maxSubarray' maxSoFar maxEndingHere i start end (x:xs) =
let i' = i + 1
maxEndingHere' = maxEndingHere + x
in
if (maxSoFar < maxEndingHere')
then maxSubarray' maxEndingHere' maxEndingHere' i' start i xs
else
if maxEndingHere' < 0
-- reset the subarray we are checking
then maxSubarray' maxSoFar 0 i' i' i' xs
else maxSubarray' maxSoFar maxEndingHere' i' start end xs
You can see that the amount of values we need to pass to the function is increasing. This makes it harder to read and keep track of the values. In the future, for more complex algorithms we might consider some monadic tools like Reader
, Writer
and State
to reduce the complexity. We will test maxSubarray
below and take a look at some of the results.
test = [-2, -3, 4, -1, -2, 1, 5, -3]
test2 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
test3 = [1,2,3,4,5]
test4 = [1,2,3,4,5, -5]
main :: IO ()
main = do
print $ maxSubarray test -- (7, 2, 6)
print $ maxSubarray test2 -- (6, 3, 6)
print $ maxSubarray test3 -- (15, 0, 4)
print $ maxSubarray test4 -- (15, 0, 4)