DÚ: nejdelší segment

Naprogramujte funkci která najde v daném seznamu čísel nejdelší segment s kladným součtem.

Body podle složitosti řešení: kvadraticky za polovinu, lineárně za plný počet (3, případně různé stavy mezi).

Nápověda: jak poznat zda se vybraný segment dá nějak prodloužit (doprava)?

import Data.Maybe (mapMaybe)
import System.Random (mkStdGen, randoms)

segment xs = let
	--create a list of cumulative sums
	cumSum = scanl (+) 0 xs
	-- lists of prefix minimums and suffix maximums of cumulative sums
	pmaxs_cs = scanl1 min cumSum
	smins_cs = scanr1 max cumSum
	-- walk the lists above simultaneously so that minVal < maxVal,
	-- and remember the best result so far (both lists are descending)
	--fBest :: (Int,[Int]) -> (Int,[Int]) -> [Int] -> [Int] -> [Int]
	fBest now@(nLen,nStart) best@(bLen,bStart) aMins@(min0:mins) aMaxs@(max0:maxs)
		| min0 <= max0 = fBest (nLen+1,nStart)      (max now best) aMins maxs
		| otherwise   = fBest (nLen-1,tail nStart) best           mins  aMaxs
	fBest _ (bLen,bStart) _ _ = take bLen bStart

	in fBest (0,xs) (0,xs) pmaxs_cs smins_cs

Bonus k zamyšlení: má řešení O(1) prostorovou složitost? Pořadí vyhodnocování v Haskellu je líné (kousky hodnot se nevyhodnocují dokud nejsou potřeba) a paměť na kterou tranzitivně neodkazujeme se nepočítá (sežere ji GC).

{-
import Data.Maybe (mapMaybe)
import System.Random (mkStdGen, randoms)
-- -}
test = mapMaybe mkMsg
	[ ([-9, 0, 1, 0, 0, 0,-1, 1,-9], [0, 1, 0, 0, 0,-1, 1], "one negative")
	, ([-9, 0, 1, 0, 0, 0,-2,-1,-9], [0, 1, 0, 0, 0], "all positive")
	, ([-9, 0, 1, 0, 0, 0,-1, 0,-9], [0, 1, 0, 0, 0], "no zero sum")
	] where
		mkMsg a@(inp,outp,msg)
			| segment inp == outp = Nothing
			| otherwise = Just $ show a ++ show (segment inp)

mkRL :: Int -> [Int]
mkRL len = take len $ map ((+ (-6)) . (`mod` 10)) $ randoms (mkStdGen 1381256)

testR4 = segment (mkRL 1234) ==
	[ 2,0,2,1,-4,3,0,3,-6,1,3,2,1,2,2,-6,-6,-6,-5,1,
		0,3,2,1,-2,1,1,3,1,-4,2,2,-2,3 ]
testR5 = segment (mkRL 12345) ==
	[ 0,1,2,2,0,-2,-5,2,2,2,-2,2,3,2,1,-4,-4,3,0,3,3,
		-1,1,-2,1,2,-1,-1,0,3,1,0,-3,-6,-3,-1,-5,3,3 ]
testR6 = result == res1 || result == res2 where
	result = segment (mkRL 123456)
	res1 = [ 3,3,-1,1,3,3,-1,1,-2,-4,2,-3,3,1,3,1,2,2,0,0,-4,3,0,-1,3,0,
		-4,-1,1,-1,3,1,3,-5,-5,-4,3,3,-6,1,2,1,1,0,-5,1,-1,-4 ]
	res2 = [ -5,3,3,-1,1,3,3,-1,1,-2,-4,2,-3,3,1,3,1,2,2,0,0,-4,3,0,-1,
		3,0,-4,-1,1,-1,3,1,3,-5,-5,-4,3,3,-6,1,2,1,1,0,-5,1,-1 ]
testR7 = result == res1 || result == res2 where
	result = segment (mkRL 1234567)
	res1 = [ -5,-3,2,-3,0,-2,-2,-1,3,-1,1,3,-1,-4,2,-3,1,-3,3,1,-1,1,-5,3,-1,1,3,3,
		-2,2,0,3,-2,2,1,3,1,-4,3,3,2,3,-1,1,2,-6,-4,0,3,0,-1,3,3,-4,-5,-4,
		-2,2,-5,2,1,-1,3,-1,3,2,3,2,0,-3,-3,1,1,3,1,-2,0 ]
	res2 = [ 2,-3,0,-2,-2,-1,3,-1,1,3,-1,-4,2,-3,1,-3,3,1,-1,1,-5,3,-1,1,3,3,-2,2,
		0,3,-2,2,1,3,1,-4,3,3,2,3,-1,1,2,-6,-4,0,3,0,-1,3,3,-4,-5,-4,-2,2,-5,2,1,
		-1,3,-1,3,2,3,2,0,-3,-3,1,1,3,1,-2,0,-6,-3 ]