Leetcode 300 Longest Increasing Subsequence

Datetime:2016-08-23 01:21:10          Topic: LeetCode           Share

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?

基本DP, dp数组代表当前位置最长序列长度,状态转移方程为

dp[i] = max(dp[i],dp[j]+1)
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        dp = [1 for x in range(len(nums))]
        ans = 1
        for i in range(1,len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i],dp[j]+1)
            ans = max(ans,dp[i])
        return ans




About List