# 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))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/dynamic-programming/300longest-increasing-subsequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.