--0-1730055050-11852992043873
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit

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  rr[0]
     min_prefix  rr[0] < 0 ? arr[0] : 0
     # Maximum sum so far.
     max_sum  refix
     # Current candidate and low/high indices.
     idx_l_candidate  rr[0] < 0 ? 0 : -1
     idx_l  1
     idx_h  
     for i in 1...arr.length
        # New prefix.
        prefix + rr[i]
        # If the sum is maximal so far, we have new candidate.
        if prefix - min_prefix > max_sum
          max_sum  refix - min_prefix
          idx_l  dx_l_candidate
          idx_h  
        end
        # New prefix if lower then current one.
        if prefix < in_prefix
          min_prefix  refix
          idx_l_candidate  
        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  Q131.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  Q131.max_sub_array arr
     assert_equal([1], msa)
  end

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

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

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

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

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

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

  def test_max_sub_array8
     arr  -1, 2, -3, 4, -5, 6]
     msa  Q131.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  Q131.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. 
--0-1730055050-11852992043873--