aboutsummaryrefslogtreecommitdiffstats
path: root/300
diff options
context:
space:
mode:
authorterminaldweller <thabogre@gmail.com>2022-08-08 06:12:16 +0000
committerterminaldweller <thabogre@gmail.com>2022-08-08 06:12:16 +0000
commit891ea0cb9507adf11f2f980168f31f1c869d8319 (patch)
treed57266a0bfabf789058f57ec466e12ebe8149ae7 /300
parentupdate (diff)
downloadleetcode-891ea0cb9507adf11f2f980168f31f1c869d8319.tar.gz
leetcode-891ea0cb9507adf11f2f980168f31f1c869d8319.zip
update
Diffstat (limited to '300')
-rwxr-xr-x300/main.py36
1 files changed, 36 insertions, 0 deletions
diff --git a/300/main.py b/300/main.py
new file mode 100755
index 0000000..f079abe
--- /dev/null
+++ b/300/main.py
@@ -0,0 +1,36 @@
+#!/usr/bin/env python3
+# https://scribe.rip/codex/leetcode-300-longest-increasing-subsequence-b5eaba41e407
+
+
+from typing import List
+
+
+class Solution:
+ def lengthOfLIS(self, nums: List[int]) -> int:
+ dp = [0] * len(nums)
+ dp[0] = 1
+
+ maximum: int = 1
+
+ for i in range(0, len(dp)):
+ dp[i] = 1
+ for j in range(0, i):
+ if nums[i] > nums[j]:
+ if dp[j] + 1 > dp[i]:
+ dp[i] = dp[j] + 1
+
+ if dp[i] > maximum:
+ maximum = dp[i]
+
+ return maximum
+
+
+def main():
+ solution = Solution()
+ print(solution.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))
+ print(solution.lengthOfLIS([0, 1, 0, 3, 2, 3]))
+ print(solution.lengthOfLIS([7, 7, 7, 7, 7, 7, 7]))
+
+
+if __name__ == "__main__":
+ main()