> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/ix.-dynamic-programming/300.-longest-increasing-subsequence.md).

# 300. Longest Increasing Subsequence

\# Medium（非常经典，一定要会）

{% hint style="success" %}
This is type of sequence DP. ***前\*\*\*\*`i`****个是否是****`LIS`\*\*\*\*. 这也叫区间动态规划，下角标从小到大计算，因为后面的元素基于前面的元素。***

From index of `0` to `n`, record longest increasing subsequence in a list. `f[i]` means the longest increasing subsequence ending with `nums[i]`. 
{% endhint %}

### Solution 1: time complex = $$O(n^2)$$ 

1. Define `f[i]`, records the longest increasing subsequence ending with `nums[i]`
2. Compute `f[i]` from index of `0`, `if nums[j] < nums[i] (j < i), f[i]=max(f[i], f[j]+1)`
3. Loop `f[i]` to find biggest value, return it

{% tabs %}
{% tab title="Python(O(n^2))" %}

```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # edge case
        if len(nums) <= 1:
            return len(nums)
        
        f = [1]*len(nums) # f[i] means LIS ending with nums[i]
        for i in range(0, len(nums)):
            for j in range(0, i):
                if nums[j] < nums[i]:
                    f[i] = max(f[i], f[j]+1)
        
        result = f[0]
        for i in range(1, len(f)):
            if f[i] > result:
                result = f[i]
                
        return result
```

{% endtab %}

{% tab title="Java(O(n^2))" %}

```java
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] longest = new int[nums.length];
        Arrays.fill(longest, 1);
        
        for(int i = 1; i < nums.length; i ++) {
            for(int j = 0; j < i; j ++) {
                if(nums[j] < nums[i])
                    longest[i] = Math.max(longest[i], longest[j]+1);
            }
        }
        Arrays.sort(longest);
        return longest[nums.length - 1];
    }
}
```

{% endtab %}
{% endtabs %}

### Solution 2: time complex = $$O(nlgn)$$&#x20;

> Save time when looking for the biggest element `nums[j]` less than `nums[i]` by binary search.&#x20;

{% tabs %}
{% tab title="Java" %}

```java
class Solution {
    public int lengthOfLIS(int[] nums) {
        // sub is always an ascending list
        ArrayList<Integer> sub = new ArrayList<>();
        sub.add(nums[0]);
        for(int i = 1; i < nums.length; i ++) {
            if(nums[i] > sub.get(sub.size() - 1))
                sub.add(nums[i]);
            else {
                int x = insertPosition(sub, nums[i]);
                sub.set(x, nums[i]);
            }
        }
        return sub.size();
    }
    
    // fint the element is just lagger than target
    // then replace it with target
    private int insertPosition(ArrayList<Integer> sub, int target) {
        int left = 0, right = sub.size() - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(target == sub.get(mid))
                return mid;
            else if(target > sub.get(mid))
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
}
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}