Personal tools

Haskell Quiz/Maximum Sub-Array/Solution Kristof

From HaskellWiki

< Haskell Quiz | Maximum Sub-Array(Difference between revisions)
Jump to: navigation, search
Current revision (19:50, 11 August 2007) (edit) (undo)
 
(One intermediate revision 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 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 position (<hask>r</hask> and <hask>rsum</hask>).
<haskell>
<haskell>

Current revision

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)
Retrieved from "http://www.haskell.org/haskellwiki/Haskell_Quiz/Maximum_Sub-Array/Solution_Kristof"