On Sun, 15 Jul 2007 21:30:59 +0900, Aureliano Calvo wrote:

> Given that the spoiler time is finished (I think) these are my
> solutions to the Quiz #131. 

And here is mine, which I think it's the same of your solution #3.

If I understand the problem correctly this is a known problem and 
finding the optimal solution is a classic example of Dynamic Programming
(where programming = planning, no relation with eval & duck typing).

But I solved it some time ago with TDD finding an cool case
where test-first finds an optimal algorithm, so it may be interesting to
report it. Notice that I start finding the maximum subsequence value,
well'keep track of the indexes later. 


#max.rb, step 1. I use variable length arguments instead of array objects.

  if __FILE__ == $0
    require 'test/unit'
    class TC < Test::Unit::TestCase
      alias is assert_equal 
      def test_maxseq
        is 0, maxseq(0)
      end
    end
  end

# ok, test fails cause no maxseq exists, yet
# step 2

  def maxseq(*ary)
    total=0
  end

# passes, step 3:

  def test_maxseq
    is 0, maxseq(0)
    is 3, maxseq(0,1,2)
  end

# fails, we need a sum:
  def maxseq(*ary)
    total=0
    ary.each {|el| total+=el}
    total
  end

# ok now passes again, try with a negative number:
  def test_maxseq
    is 0, maxseq(0)
    is 3, maxseq(0,1,2)
    is 0, maxseq(-1), "we choose 0 if we have only negative values"
  end

# return 0 if adding means getting a smaller result
  def maxseq(*ary)
    total=0
    ary.each {|el| total=[total+el,0].max} 
    total
  end

# ok, passes again, let's add some more complex sequences:
      is 6, maxseq(1,2,3)
      is 3, maxseq(1,-2,3)
      is 3, maxseq(1,2,-3)

# mh.. the last fails, because we return 0.. we should keep the
current value, which will be zero at the beginning:

def maxseq(*args)
  total=0
  current=0
  args.each do |el|
    current=[current+el,0].max
    total=[total,current].max
  end
  total
end

# now let's throw some more stuff at it:
    def test_maxseq
      is 0, maxseq(0)
      is 3, maxseq(0,1,2)
      is 0, maxseq(-1), "we choose [] if we have only negative values"
      is 6, maxseq(1,2,3)
      is 3, maxseq(1,-2,3)
      is 3, maxseq(1,2,-3)
      is 3, maxseq(1,2,-3)
      is 5, maxseq(-1,2,3)
      is 0, maxseq(-1,-2)
      is 8, maxseq(1,-2,3,4,-5,6,-7)
      is 6, maxseq(1,-2,-3,6)
      is 11,maxseq(0,1,-2,-3,5,6)
    end

And then you realize.. well, it works, no need for complications, and it
runs in linear time, which is pretty good, compared to the naive approach
of trying all possible subsequences. 

Now, to make it a dirty oneliner:
def maxseq(*ary) 
  ary.inject([0, 0]) {|(t, c), e| [[t, c=[c+e, 0].max].max, c]}.first
end

and all tests still pass :)

By this point it is trivial to keep track of the indexes:

def maxseq_indexes(*args)
  # total now means "total value, where they start, where they finish"
  total = start = finish = 0
  # current too
  current = curr_start = curr_finish =0
  args.each_with_index do |el,idx|
    if current+el >= 0
      current+=el
      curr_finish = idx
    else
      current = 0
      curr_start = idx+1
    end
    if current >= total
      total = current
      start  = curr_start
      finish = curr_finish
    end
  end
  total.zero? ? [] :  args[start..finish] 
end

and its tests:
    def test_maxseq_indexes2
      is [], maxseq_indexes(0)
      is [0,1,2], maxseq_indexes(0,1,2)
      is [], maxseq_indexes(-1), "we choose [] if we have only negative values"
      is [1,2,3], maxseq_indexes(1,2,3)
      is [3], maxseq_indexes(1,-2,3)
      is [1,2], maxseq_indexes(1,2,-3)
      is [2,3], maxseq_indexes(-1,2,3)
      is [], maxseq_indexes(-1,-2)
      is [3,4,-5,6], maxseq_indexes(1,-2,3,4,-5,6,-7)
      is [6], maxseq_indexes(1,-2,-3,6)
      is [5,6],maxseq_indexes(0,1,-2,-3,5,6)
      is [2,5,-1,3], maxseq_indexes(-1, 2, 5, -1, 3, -2, 1)
    end


I'm quite sure it can be made a oneliner again, but I am busy :)



-- 
goto 10: http://www.goto10.it
blog it: http://riffraff.blogsome.com
blog en: http://www.riffraff.info