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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
# 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.