[QUIZ-Solution] Maximum Sub-Array (#131)

ruby-talk
1

Although totally algorithmic, it sounded like a nice problem. Here is my solution, based on the explanation in the text which link is given in the comments. Didn't test it too much, so don't rely on it's correctness.

Nice day to you all,
Izi

------------------ cut here

# Very nice explanation of the various algorithms about this problem:
# www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/L02.pdf
# by Mordecai J.GOLIN (PhD, Princeton, 1990)

···

#
# The algorithm below is a Ruby version of the last one,
# with additions for the index collecting.
require 'test/unit'
require 'test/unit/ui/console/testrunner'

class RQ131
  def RQ131.max_sub_array arr
     return arr if arr.length < 2
     # Current and minimum prefix.
     prefix = arr[0]
     min_prefix = arr[0] < 0 ? arr[0] : 0
     # Maximum sum so far.
     max_sum = prefix
     # Current candidate and low/high indices.
     idx_l_candidate = arr[0] < 0 ? 0 : -1
     idx_l = -1
     idx_h = 0
     for i in 1...arr.length
        # New prefix.
        prefix += arr[i]
        # If the sum is maximal so far, we have new candidate.
        if prefix - min_prefix > max_sum
          max_sum = prefix - min_prefix
          idx_l = idx_l_candidate
          idx_h = i
        end
        # New prefix if lower then current one.
        if prefix <= min_prefix
          min_prefix = prefix
          idx_l_candidate = i
        end
     end
     arr[idx_l + 1..idx_h]
  end
end

# Some unit tests.
class RQ131Test < Test::Unit::TestCase
  def test_max_sub_array1
     arr = [-1, 2, 5, -1, 3, -2, 1]
     msa = RQ131.max_sub_array arr
     assert_equal([2, 5, -1, 3], msa)
  end

  def test_max_sub_array2
     arr = [0, 0, -1, 0, 0, 1]
     msa = RQ131.max_sub_array arr
     assert_equal([1], msa)
  end

  def test_max_sub_array3
     arr = [-1, -2, -3, -4]
     msa = RQ131.max_sub_array arr
     assert_equal([-1], msa)
  end

  def test_max_sub_array4
     arr = [1, 2, 3, 4]
     msa = RQ131.max_sub_array arr
     assert_equal(arr, msa)
  end

  def test_max_sub_array5
     arr = [1, -2, 3, -4, 5, -6, 7, -8]
     msa = RQ131.max_sub_array arr
     assert_equal([7], msa)
  end

  def test_max_sub_array6
     arr = []
     msa = RQ131.max_sub_array arr
     assert_equal([], msa)

     arr = [1]
     msa = RQ131.max_sub_array arr
     assert_equal([1], msa)
  end

  def test_max_sub_array7
     arr = [0, 0, 0, 0, 0]
     msa = RQ131.max_sub_array arr
     assert_equal([0], msa)
  end

  def test_max_sub_array8
     arr = [-1, 2, -3, 4, -5, 6]
     msa = RQ131.max_sub_array arr
     assert_equal([6], msa)
  end

  def test_max_sub_array9
     arr = [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
     msa = RQ131.max_sub_array arr
     assert_equal([1, 2, 3, 4, 5], msa)
  end
end

Test::Unit::UI::Console::TestRunner.run(RQ131Test)

---------------------------------
Sick sense of humor? Visit Yahoo! TV's Comedy with an Edge to see what's on, when.