Haskell Quiz/Maximum Sub-Array/Solution Kristof
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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)