Merge pull request prabhupant#365 from durid17/LIS

prabhupant · web-flow · commit ae5a529e8bae · 2020-08-01T20:32:43.000+05:30
Longest Increasing Subsequence
diff --git a/algorithms/dynamic_programming/longest_increasing_subsequence.py b/algorithms/dynamic_programming/longest_increasing_subsequence.py
@@ -0,0 +1,13 @@
+def LIS(arr):
+    n = len(arr)
+    if n == 0: return 0
+    res = 1
+    dp = [0] * n
+    dp[0] = 1
+    for i in range(1, n): 
+        dp[i] = 1; 
+        for j in range(0 , i):
+            if arr[i] > arr[j]:
+                dp[i] = max(dp[i] , dp[j] + 1)
+        res = max(res , dp[i])
+    return res
