> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/dynamic-programming/300longest-increasing-subsequence.md).

# 300\_ Longest Increasing Subsequence

\[Medium]\[Dynamic Programming, Binary Search]

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.
```

## Solution 1:

**Idea**:

* If we know the lengths of longest increasing subsequence that end at indices 0, 1, 2, n-1, and we want to know the longest increasing subsequence that ends at index n, what shall we do?
  * We should look for look for the longest subsequence ending at any indices 0, 1, 2, n-1 whose value is less than the value at index n. Then this max length plus one will be the answer.
  * If there is no values in front of index n that is less than value at index n, the max length at index n is 1.
  * The max length for the entire array is the max of max length at all the indices.
* Can be written in iterative or recursive fashion.

**Time Complexity**: $$O(n^2)$$

**Space Complexity**: $$O(n)$$

**Iterative**:

```python
def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    output = [1] * len(nums)

    for i in range(1, len(nums)):
        output[i] = 1 + max([output[j] for j in range(i) if nums[j] < nums[i]] + [0])
        # [0] is for nothing from nums[j] is less than nums[i]
        # parameter inside max() can't be empty

    return max(output + [0])  # [0] is for empty nums
```

**Recursive**: (slow)

```python
def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    def helper(i):
        if i < 0:
            return
        elif i == 0:
            output[i] = 1
        elif output[i] == 0: 
            output[i] = 1 + max([helper(j) for j in range(i) if nums[j] < nums[i]] + [0])
        return output[i]

    output = [0] * len(nums)
    for i in range(len(nums)-1, -1, -1):
        helper(i)
    return max(output + [0])
```

## Solution 2:

**Idea**:

* Our strategy determined by the following conditions:
  * If A\[i] is smallest among all end candidates of active lists, we will start new active list of length 1.
  * If A\[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A\[i].
  * If A\[i] is in between, we will find a list with largest end element that is smaller than A\[i]. Clone and extend this list by A\[i]. We will discard all other lists of same length as that of this modified list.
* Note that at any instance during our construction of active lists, the following condition is maintained.
  * *“end element of smaller list is smaller than end elements of larger lists”*.
* Refer to [here](https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/)

**Time Complexity**: $$O(n\log{n})$$

**Space Complexity**:

```python
def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    def CeilIndex(A, l, r, key): 

        while (r - l > 1): 

            m = l + (r - l)//2
            if (A[m] >= key): 
                r = m 
            else: 
                l = m 
        return r 

    def LongestIncreasingSubsequenceLength(A, size): 

        # Add boundary case, 
        # when array size is one 

        tailTable = [0 for i in range(size+1)] 
        len=0 # always points empty slot 

        tailTable[0] = A[0] 
        len = 1
        for i in range(1, size): 

            if (A[i] < tailTable[0]): 

                # new smallest value 
                tailTable[0] = A[i] 

            elif (A[i] > tailTable[len-1]): 

                # A[i] wants to extend 
                # largest subsequence 
                tailTable[len] = A[i] 
                len+=1

            else: 
                # A[i] wants to be current 
                # end candidate of an existing 
                # subsequence. It will replace 
                # ceil value in tailTable 
                tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i] 


        return len

    return 0 if not nums else LongestIncreasingSubsequenceLength(nums, len(nums))
```