# Haskell Quiz/Maximum Sub-Array/Solution Kristof

### From HaskellWiki

< Haskell Quiz | Maximum Sub-Array(Difference between revisions)

m |
|||

Line 1: | Line 1: | ||

− | This solution uses a left fold find the maximum sum. It keeps track of the maximum sublist found so far (the list <hask>max</hask> and it's sum <hask>sum</hask>), and the maximum sublist that includes the rightmost number (<hask>r</hask> and <hask>rsum</hask>). |
+ | This solution uses a left fold to find the maximum sum. It keeps track of the maximum sublist found so far (the list <hask>max</hask> and it's sum <hask>sum</hask>), and the maximum sublist that contains the current number (<hask>r</hask> and <hask>rsum</hask>). |

<haskell> |
<haskell> |

## Revision as of 19:47, 11 August 2007

This solution uses a left fold to find the maximum sum. It keeps track of the maximum sublist found so far (the listmax

sum

r

rsum

max_sublist l = reverse $ fst $ foldl find_max ([],(0,[],0)) l where find_max (max, (sum, r, rsum)) x = (max', (sum', r', rsum')) where (r', rsum') = if (rsum > 0) then (x:r, rsum+x) else ([x], x) (max', sum') = if (rsum' > sum) then (r', rsum') else (max, sum)