diff options
Diffstat (limited to 'longest_increasing_subseq.py')
-rw-r--r-- | longest_increasing_subseq.py | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/longest_increasing_subseq.py b/longest_increasing_subseq.py new file mode 100644 index 0000000..0547dbf --- /dev/null +++ b/longest_increasing_subseq.py @@ -0,0 +1,28 @@ +# 300. Longest Increasing Subsequence + +""" +given an integer array 'nums', return the length of the longest strictly +increasing subsequence. +""" + + +class Solution(object): + def lengthOfLIS(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + n = len(nums) + dp = [1] * n + for i in range(1, n): + for j in range(i): + if nums[i] > nums[j]: + dp[i] = max(dp[i], dp[j] + 1) + return max(dp) + + +if __name__ == "__main__": + obj = Solution() + print(obj.lengthOfLIS(nums=[10, 9, 2, 5, 3, 7, 101, 18])) # expect: 4 + print(obj.lengthOfLIS(nums=[0, 1, 0, 3, 2, 3])) # expect: 4 + print(obj.lengthOfLIS(nums=[7, 7, 7, 7, 7, 7, 7])) # expect: 1 |