import Data.List ( inits, tails, unfoldr )
import Control.Parallel
import Data.Foldable ( foldl', foldr' )
import System.Random
import System.Environment
import GHC.Conc ( numCapabilities )
import Test.SmallCheck
main = do
[ nn ] <- getArgs
xs <- some_other_sequence $ read nn
print $ sum xs
let caps = GHC.Conc.numCapabilities
print caps
print $ sss_f caps xs
some_other_sequence n = return $ take n
$ unfoldr ( \ x -> seq x $ Just ( x, mod (113 * x + 558) 335 - 167 ) ) 0
some_sequence n = do
g <- newStdGen
let xs :: [ Int ]
xs = take n
$ randomRs ( -10,10) g
return xs
sss xs = maximum $ do
ys <- tails xs
zs <- inits ys
return $ sum zs
prop_sss f xs = sss xs == f xs
sss_fl :: [Int] -> Int
sss_fl = snd .
foldl' ( \ (here, total) x ->
let here' = max x ( here + x )
in ( here', max here' total ) )
(0,0)
sss_fr :: [Int] -> Int
sss_fr = snd .
foldr' ( \ x (here, total) ->
let here' = max x ( here + x )
in ( here', max here' total ) )
(0,0 )
data O = O { s :: ! Int, l :: !Int, r :: !Int , t :: !Int }
sss_f caps = t
. foldb caps
( \ o1 o2 ->
let s' = s o1 + s o2
r' = max (r o2) ( s o2 + r o1 )
l' = max (l o1) ( s o1 + l o2 )
t' = max (r o1 + l o2)
$ max ( t o1 ) ( t o2 )
in O { s = s', r = r', l = l', t = t' }
) ( \ x -> O { s = x, r = max x 0, l = max x 0, t = max x 0} )
( O { s = 0, r = 0, l = 0, t = 0 } )
foldb caps f u e xs =
if caps > 0
then case xs of
[ ] -> e
[x] -> u x
_ -> let
( lo, hi ) = splitAt ( div (length xs) 2 ) xs
x = foldb (div caps 2 ) f u e lo
y = foldb (div caps 2 ) f u e hi
in par x $ pseq y $ f x y
else foldl' f e ( map u xs )