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 )