300.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

# Author: Yu Zhou
# 300. Longest Increasing Subsequence

# DP O(N^2)
# 状态：到目前f[i]点为止，经过比较，从 0 ->i 最大的 的List
# 方程： if num[i] > num[j] :
# get the max of (dp[i], dp[j]+1) 因为dp[i]很可能会比dp[j]+1 大


classSolution(object):
deflengthOfLIS(self, nums):
"""
 :type nums: List[int]
 :rtype: int
 """

# Edge
ifnotnums:
return0

# Creating DP
dp= [1foriinxrange(len(nums))]

foriinxrange(len(nums)):
forjinxrange(i):
ifnums[j] <nums[i]:
ifdp[j] +1>dp[i]:
dp[i] =dp[j] +1

returnmax(dp)