[300] Longest Increasing Subsequence

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

• algorithms
• Medium (39.63%)
• Source Code: 300.longest-increasing-subsequence.py
• Total Accepted: 210.9K
• Total Submissions: 520.4K
• Testcase Example: '[10,9,2,5,3,7,101,18]'

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

Example:

Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

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?

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] and DP[i] < DP[j] + 1:
                    DP[i] = DP[j] + 1
        return max(DP)


# [-2, -1]