leetcode 300. 最长递增子序列

大致思路：动态规划
列如 n=[4,10,4,3,8,9]
1.初始化，dp=[1,1,1,1,1,1]；
2.要想知道 n的最长递增子序列，需要推出[10,4,3,8,9]的最长递增子序列，……，需要推出[9]的最长递推子序列。
此时等于是将n做了一个划分：划分为 4 和 [10,4,3,8,9]
10 和[4,3,8,9]
……
8 和[9]

[1, 1, 1, 1, 2, 1]
[1, 1, 1, 3, 2, 1]
[1, 1, 3, 3, 2, 1]
[1, 1, 3, 3, 2, 1]
[3, 1, 3, 3, 2, 1]

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):
            # print nums[n-1-i],nums[n-i:n]
            pos=-1
            m=-1
            for j in range(n-i,n):
                if nums[n-1-i]<nums[j] and m<dp[j]:
                    pos=j
                    m=dp[j]
            if pos!=-1:
                dp[n-1-i]=dp[pos]+1
        #     print dp 
        # print dp
        m=-1
        for i in range(0,n):
            if m<dp[i]:
                m=dp[i]
        return m