```--0-1730055050-11852992043873
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

# 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-11852992043873--

```