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
 """
 ...

• 301_Moved_Permanently: "Use range instead of xrange"? The very use of xrange indicates this is Python 2 where xrange (generator) is recommended over range (building a list in memory upfront).