> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0300_longest_increasing_subsequence/slt.md).

# Solution 1 DP

* t-comlpexity: O(n^2)
* s-comlpexity: O(n)

dp\[i] represents LIS ending with i.

```
max_len = 1
for i in range(n):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j]+1)
    max_len = max(max_len, dp[i])
```