4 Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, Input [10, 9, 2, 5, 3, 7, 101, 18]

LIS is [2, 3, 7, 101].

Return 4

Your algorithm should run in O(n2) complexity.

思路： dp[i]代表nums[0:i]的LIS。有点像1维DP。其实是2D DP。如果第i个数，比第k个数大，那么dp[i]=dp[k]+1, 可是如果比前面好多数大怎么办。那么就需要取前面所有dp里面值最大的+1。毕竟+1秒我们要加在最长者的地方。

递推公式是：dp[i] = max(dp[k] for k in [0:i-1] if nums[i]>nums[k]) + 1秒

LC https://leetcode.com/problems/longest-increasing-subsequence/

jiuzhang http://www.lintcode.com/en/problem/longest-increasing-continuous-subsequence/

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        dp = [1]*len(nums)

        for i in range (1, len(nums)):
            for j in range(i):
                if nums[i] >nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)

        return max(dp)

Follow up：为什么1D array你说是 n^2的复杂度。 答：因为每更新一个，都要把前面的全部扫一遍。n(n-1)/2 = O(n^2)