The Haskell Program: G_profits/profits.hs

  1 {-
  2  SER 2010.  Problem G: Profits
  3  Author: Ryan Stansifer
  4-}
  5 
  6 {-# OPTIONS_GHC -Wall -Werror -O2 #-}
  7 
  8 module Main where
  9 
 10 import Text.Printf        -- import text formating function
 11 
 12 main :: IO()
 13 main = interact (showResults . map solve . readTestCases)
 14 
 15 type InstanceType = [Int]
 16 type ResultType = Int
 17 
 18 {-
 19-- Show the results of all the test cases
 20-}
 21 showResults :: [ResultType] -> String
 22 showResults = unlines . (map format)
 23   where format n = printf "%d" n
 24 
 25 {-
 26-- Break up the entire input into the test cases
 27-}
 28 readTestCases :: String -> [InstanceType]
 29 readTestCases = parse0 . (map read) . words
 30 
 31 -- Break the input up into a list of individual test cases
 32 parse0 :: [Int] -> [InstanceType]
 33 parse0 [0]      = []
 34 parse0 (n:rest) = (take n rest) : (parse0 (drop n rest)) 
 35 parse0 _        = error "Illegal input"
 36 
 37 {-
 38-- Solve the problem for one test case
 39-}
 40 solve :: InstanceType -> ResultType
 41 solve xs = snd (foldr combine (0,-100) xs)
 42 
 43 -- combine the profit of an individual day with the best sequence
 44 -- ending here and keep the optimal sum overall.
 45 combine :: Int -> (Int,Int) -> (Int,Int)
 46 combine p (total,opt) =
 47    let y=max (total+p) p in (y, max y opt)