max_subseq.rb

class MaxSubseq
  class Seq < Struct.new(:array, :sum)
    class << self
      def empty
        new([], 0)
      end
    end

    def append(x)
      self.class.new(array + [x], sum + x)
    end
  end

  attr_reader :sequence

  def initialize(sequence)
    @sequence = sequence
  end

  def find
    global_mss = Seq.empty
    suffix_mss = Seq.empty

    global, _suffix = sequence.reduce([global_mss, suffix_mss]) do |(gs, ss), n|
      current_ss = ss.append(n)
      if current_ss.sum > gs.sum
        [current_ss, current_ss]
      else
        if current_ss.sum < 0
          [gs, Seq.empty]
        else
          [gs, current_ss]
        end
      end
    end

    global
  end
end

puts '=' * 78
sample1 = [2, -3, 1.5, -1, 3, -2, -3, 3]
puts MaxSubseq.new(sample1).find

puts '=' * 78
sample2 = [-2, -3, -1.5, -1, -3, -2, -3, -3]
puts MaxSubseq.new(sample2).find

puts '=' * 78
sample3 = [1]
puts MaxSubseq.new(sample3).find

puts '=' * 78
sample4 = [4, -3, 1, 0, -0.1, 99, -1, 2]
puts MaxSubseq.new(sample4).find

maxSubseq.hs

module MaxSubseq (maxSubseq) where
import Prelude hiding (seq, sum)

data Seq = Seq { seq::[Double], sum::Double } deriving Show
instance Eq Seq where
  (Seq _ x) == (Seq _ y) = x == y

instance Ord Seq where
  (Seq _ x) <= (Seq _ y) = x <= y

emptySeq :: Seq
emptySeq = Seq [] 0

prepend :: Seq -> Double -> Seq
prepend (Seq xs s) x = Seq (x:xs) (s + x)

maxSubseq :: [Double] -> [Double]
maxSubseq = (seq . fst . foldr findSeq (emptySeq, emptySeq))
  where
    findSeq x (gs, ps) =
      let
        currentPs = prepend ps x
      in
        (max currentPs gs, max currentPs emptySeq)