{-# LANGUAGE BangPatterns #-} {-# LANGUAGE BinaryLiterals #-} {-# LANGUAGE MultiWayIf #-} {-# LANGUAGE NumDecimals #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TupleSections #-} import Control.Applicative import Control.Arrow import Control.Monad import Control.Monad.ST import Data.Char import Data.List import Data.Maybe import qualified Data.ByteString.Char8 as B import Data.Array.ST.Safe import Data.STRef import Debug.Trace import Text.Printf readInt = readLn :: IO Int readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine readNInts = readInt >>= flip replicateM readInt which a b f = if f then a else b mp [ a, b ] = ( a, b ) modifyArray array pos f = writeArray array pos =<< f <$> readArray array pos main = do plusminus <- map ( \c -> if c == 'A' then 1 else -1 ) <$> getLine let psum = scanl (+) 0 plusminus print $ maximum $ map maxdiff $ solve psum solve psum = runST $ do let n = succ $ length psum occurrences <- newArray ( -n, n ) [] :: ST s ( STArray s Int [Int] ) forM_ ( zip psum [ 0 .. ] ) $ \( value, pos ) -> modifyArray occurrences value ( pos : ) getElems occurrences maxdiff [] = 0 maxdiff as = head as - last as