Haskell Quiz/Maximum Sub-Array/Solution Kristof
Jump to navigation
Jump to search
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 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)