边工作边刷题：70天一遍leetcode: day 31-4

Longest Increasing Subsequence

leetcode上这道题目本身不难，虽然有，但是O(n^2)的dp足够应付面试了。

补充 4/30/16
google考这题增加了不少扩展：

• 如何print一个longest的结果：这个我们可以用dp的回溯，需要另一个数组记录每步的选择点
• 所有longest的组合。dp基础上，需要用list来记录所有选择
• recursion怎么搞? 首先对于有dp解的，想recursion要从反方向走，对于这题就是从整个数组开始

ref:

• http://www.mitbbs.com/article_t/JobHunting/33176505.html
• Programming Interview 49: Print Longest Increasing Subsequence (LIS) using Dynamic Programming - YouTube https://www.youtube.com/watch?v=SZByPn0deMY

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        maxLen = 1
        n = len(nums)
        dp = [1 for i in range(n)]
        dp[0]=1
        for i in range(1,n):
            for j in range(i):
                if nums[i]>nums[j]:
                    if dp[j]+1>dp[i]:
                        dp[i]=dp[j]+1
            
            if dp[i]>maxLen:
                maxLen = dp[i]
        
        return maxLen