# Maximum Subarray in Haskell

2018-12-29

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)``````