# Find the Maximum Sum of a Contiguous Subsequence in a List

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


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

• "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). – 301_Moved_Permanently Aug 2 '18 at 20:17
• @MathiasEttinger good point, I clarified, thanks – janos Aug 2 '18 at 20:21