Longest Increasing Subsequence

Problem: Longest Increasing Subsequence

The solution just construct a 2D array and do dynamic programming.

Code in Python:

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

The O(nlogn) binary search solution just convert this problem to a sorting problem. We can use binary search to find the right insertion position of a new number and the running time will become O(nlogn).