Created
March 28, 2019 02:05
-
-
Save tslmy/d2089a4e648dd0a9b79a46cbe401e312 to your computer and use it in GitHub Desktop.
Printing Maximum Sum Increasing Subsequence
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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