leetcode dynamic programming

300. Longest Increasing Subsequence

Question

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

For example,

Given

[10, 9, 2, 5, 3, 7, 101, 18],

The longest increasing subsequence is

[2, 3, 7, 101]

, therefore the length is

4

. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Solution

dp[i] means the length of an increase sequence that includes nums[i], and it must equals a previous dp value add one which reaches the max.

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [1]*len(nums)
        for i in xrange(len(nums)):
            for y in xrange(i):
                if nums[i] >nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp) if dp else 0