November 3, 2017

# Python maximum contiguous subsequence sum

For definition and explanation please refer to the following post. This post is only implementation in Python.

**Python code**

# Function recieves the input array A def MCSS (A): # Auxiliary array B = [] # MCSS ending at position 0 is just the first element B.append(A[0]) # Populate B for i in range (1, len(A)): # MCSS ending at position i is the max of # B[i-1] + A[i] and A[i] so B[i-1] > 0 is the # same as B[i-1] + A[i] > A[i] if B[i-1] > 0: B.append(B[i-1] + A[i]) else: B.append(A[i]) # Find the max value in B max = B[0] for i in range(len(A)): if B[i] > max: max = B[i] return max # Sample array A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] # Print MCSS print "MCSS = {}".format(MCSS(A))

If you run the code snippet above you should get 6. Thanks for reading. Please use the comments section below for questions.