1
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
    """
    ...
\$\endgroup\$
  • \$\begingroup\$ "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). \$\endgroup\$ – Mathias Ettinger Aug 2 '18 at 20:17
  • \$\begingroup\$ @MathiasEttinger good point, I clarified, thanks \$\endgroup\$ – janos Aug 2 '18 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.