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
The translation to Haskell is pretty simple. Instead of two mutable values, we create an internal function that takes the updated values of
maxEndingHere and call it recursively over the values of the list and when the list is empty, we return the
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
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)