Fork me on GitHub

Longest Increasing Subsequence

Posted on

Description

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

Example:

1
2
3
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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        lens = len(nums)
        if not lens:
            return 0
        
        end_array = [0 for i in range(lens)]
        end_array[0] = 1
        max_length = 1
        for end in range(1, lens):
            local_max_length = 1
            for start in range(0, end):
                if nums[start] < nums[end]:
                    if end_array[start] + 1 > local_max_length:
                        local_max_length = end_array[start] + 1
            
            end_array[end] = local_max_length
            if max_length < local_max_length:
                max_length = local_max_length
            
        return max_length