content: -- MaxSum.hs
  -- Copyright (C) 2013 Liu Xinyu (liuxinyu95@gmail.com)
  -- 
  -- This program is free software: you can redistribute it and/or modify
  -- it under the terms of the GNU General Public License as published by
  -- the Free Software Foundation, either version 3 of the License, or
  -- (at your option) any later version.
  -- 
  -- This program is distributed in the hope that it will be useful,
  -- but WITHOUT ANY WARRANTY; without even the implied warranty of
  -- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  -- GNU General Public License for more details.
  -- 
  -- You should have received a copy of the GNU General Public License
  -- along with this program.  If not, see <http://www.gnu.org/licenses/>.
  
  module MaxSum where
  
  import Data.List (inits, tails)
  import Test.QuickCheck
  
  maxsum = msum 0 0 where
    msum a _ [] = a
    msum a b (x:xs) = let b' = max (x+b) 0
                          a' = max a b'
                      in msum a' b' xs
                         
  bruteMaxSum = maximum . (map sum) . concat . (map inits) . tails
  
  -- Note that the type has to be Integer to handle sum overflow
  prop_maxsum :: [Integer] -> Bool
  prop_maxsum xs = bruteMaxSum xs == maxsum xs
  