Find the Maximum Sum of a Contiguous Subsequence in a List

Question

I was given a question during interview, and I decided to code it up and learn the difference way to implement this problem. Find the Maximum Sum of a Contiguous Subsequence in a List. I was wondering if you can code review the different ways of solving this problem.

Given a list consisting of both positive and negative integers, find the maximum sum among all the contiguous subsequences of the input list. Write a function that takes in a list of integers and returns the maximum sum.

#  Example:   input = [6, -1, 3, 5, -10]
#             output = 13 (6 + -1 + 3 + 5 = 13)

another example.

#maxSubArraySum([-1,-2,3,4,5]) ==> 12

#maxSubArraySum([1,2,3,-2,5]) ==> 9

my first solution

def maxSubArraySum(arr):

    max_so_far =arr[0]
    curr_max = arr[0]

    for i in range(1,len(arr)):
        curr_max = max(arr[i], curr_max + arr[i])
        max_so_far = max(max_so_far,curr_max)

    return max_so_far

# Driver function to check the above function 
a = [-2, -3, 4, -1, -2, 1, 5, -3]
print"Maximum contiguous sum is" , maxSubArraySum(a)

my second solution Dynamic programming solution

def maxSubArraySum(nums):
  if not nums: return 0
  n = len(nums)
  s = [0] * n
  res, s, s_pre = nums[0], nums[0], nums[0]
  for i in xrange(1, n):
      s = max(nums[i], s_pre + nums[i])
      s_pre = s
      res = max(res, s)
  return res

it passes all the test

# input: count {List} - keeps track out how many tests pass and how many total
#        in the form of a two item array i.e., [0, 0]
# input: name {String} - describes the test
# input: test {Function} - performs a set of operations and returns a boolean
#        indicating if test passed
# output: {None}
def expect(count, name, test):
    if (count is None or not isinstance(count, list) or len(count) != 2):
        count = [0, 0]
    else:
        count[1] += 1

    result = 'false'
    error_msg = None
    try:
        if test():
            result = ' true'
            count[0] += 1
    except Exception as err:
        error_msg = str(err)

    print('  ' + (str(count[1]) + ')   ') + result + ' : ' + name)
    if error_msg is not None:
        print('       ' + error_msg + '\n')


print('max_consecutive_sum Tests')
test_count = [0, 0]


def test():
    example = max_consecutive_sum([6, -1, 3, 5, -10])
    return example == 13


expect(test_count, 'should work on example input', test)


def test():
    example = max_consecutive_sum([5])
    return example == 5


expect(test_count, 'should work on single-element input', test)


def test():
    example = max_consecutive_sum([])
    return example == 0


expect(test_count, 'should return 0 for empty input', test)


def test():
    example = max_consecutive_sum([-1, 1, -3, 4, -1, 2, 1, -5, 4])
    return example == 6


expect(test_count, 'should work on longer input', test)

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')

max_consecutive_sum Tests
  1)    true : should work on example input
  2)    true : should work on single-element input
  3)    true : should return 0 for empty input
  4)    true : should work on longer input
PASSED: 4 / 4

Answer 1

The first solution is quite fine, with minor issues:

• It doesn't support empty list
• Instead of for i in range(1,len(arr)):, it would be simpler to for value in arr[1:]:
• Formatting and function naming doesn't follow PEP8

Given that the first solution is simple and efficient, I don't see much point in a second solution that uses \$O(n)\$ extra storage. Other minor issues with it:

• It's strongly recommended to use consistent indent width (preferably 4 spaces)
• It's recommended to use a line break after the : in a if cond: statement
• If you are using Python 3, then use range instead of xrange
• Some comments above for the first solution apply here too

Finally, the testing code is overcomplicated, when much simpler alternatives are supported out of the box, for example doctests:

def maxSubArraySum(arr):
    """
    >>> maxSubArraySum([6, -1, 3, 5, -10])
    13
    >>> maxSubArraySum([5])
    5
    >>> maxSubArraySum([])
    0
    >>> maxSubArraySum([-1, 1, -3, 4, -1, 2, 1, -5, 4])
    6
    """
    ...