Skip to content

Instantly share code, notes, and snippets.

@tslmy
Created March 28, 2019 02:05
Show Gist options
  • Save tslmy/d2089a4e648dd0a9b79a46cbe401e312 to your computer and use it in GitHub Desktop.
Save tslmy/d2089a4e648dd0a9b79a46cbe401e312 to your computer and use it in GitHub Desktop.
Printing Maximum Sum Increasing Subsequence
def find(l):
'''Function to construct Maximum Sum Increasing Subsequence.
A rewrite of <https://www.geeksforgeeks.org/printing-maximum-sum-increasing-subsequence/>.'''
m =[[l[0]]]
for i in range(1,len(l)): # start from index 1
c = [] # "current selection"
for j in range(i): # for every j less than i
if l[i]>l[j] and sum(c)<sum(m[j]): c = m[j][:] # `[:]` is for copying, not referencing.
c.append(l[i]) # current selection only valid with selection of the current item
m.append(c)
# m[i] now stores Maximum Sum Increasing Subsequence of l[0..i] that ends with l[i]
return max(m, key=sum)
print(find([3, 2, 6, 4, 5, 1]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment