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.

Leave a Reply