trjhtr

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]) + 'nn')

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