Difference between revisions of "Haskell Quiz/Maximum Sub-Array/Solution Kristof"
Jump to navigation
Jump to search
| (One intermediate revision by the same user not shown) | |||
| 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 |
+ | 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 position (<hask>r</hask> and <hask>rsum</hask>). |
<haskell> |
<haskell> |
||
Latest revision as of 19:50, 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 list max and it's sum sum), and the maximum sublist that contains the current position (r and 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)