Skip to content

Instantly share code, notes, and snippets.

@abecus
Created August 9, 2019 17:55
Show Gist options
  • Save abecus/e87dbb8246fb9172d348f1a06fd45b61 to your computer and use it in GitHub Desktop.
Save abecus/e87dbb8246fb9172d348f1a06fd45b61 to your computer and use it in GitHub Desktop.
longest Increasing Subsequence in python
def lisArray(arr, n):
"""
returns a array of LIS
"""
dp = [[arr[0]]]
for i in range(1, n):
temp = 0
tempSubArray = []
for j in range(i):
if arr[i] > arr[j]:
if temp < len(dp[j]):
tempSubArray = dp[j]
temp = len(dp[j])
dp.append(tempSubArray+[arr[i]])
return max(dp, key=lambda x: len(x))
if __name__ == "__main__":
# l = [3,2,6,4,5,1]
l = [10 , 22 , 9 , 33 , 21 , 50 , 41 , 60]
print(lisArray(l, len(l)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment