Personal tools

Haskell Quiz/Maximum Sub-Array/Solution Kristof

From HaskellWiki

< Haskell Quiz | Maximum Sub-Array
Revision as of 10:23, 11 August 2007 by Kuribas (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
This solution uses a left fold 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 includes the rightmost number (
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)