300. Longest Increasing Subsequence
题目大意，给定一个无序的数列，求这个序列的最长单调增的子序列的长度。比如给定[10, 9, 2, 5, 3, 7, 101, 18],那么最长递增子序列为[2, 3, 7, 101] or [2, 3, 7, 18]。长度都为4.所以最后的答案是4
解题思路：
f[i] 表示子序列 [nums[0], ..., nums[i]] 里面的最长递增子序列的长度(包含nums[i])
f[i] 可以通过递归得到
for j in range(i):
if nums[j] < nums[i]:
f[i] = max(f[i], f[j] + 1)
动态规划
class Solution(object):
def lengthOfLIS(self, nums):
n = len(nums)
if n <= 1:
return n
f = [1 for _ in range(n)]
for i in range(n):
for j in range(i + 1):
if nums[j] < nums[i]:
f[i] = max(f[i], f[j] + 1)
return max(f)
这道题目还可以用记忆化递归来解，详细的讲解请参阅[解题报告] LeetCode 300. Longest Increasing Subsequence