> For the complete documentation index, see [llms.txt](https://emmaguo100.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://emmaguo100.gitbook.io/leetcode/05-21-2022-300.-longest-increasing-subsequence.md).

# 05/21/2022 300. Longest Increasing Subsequence

Method 1:

DP. Create an int array with the same length of nums and initiate it with 1. For every value in this array, it represents the length of the longest increasing subsequence for the current index.  We use two for loops. The first one iterate from i = 1 to the end of the array, while the second loop start from 0 to i - 1, if the nums\[i] > nums\[j], we update nums\[i]= Math.max(nums\[i], nums\[j] + 1). Finally loop through the result array, get the max value and return it.

Time O(n^2)

Space O(n)

```
// Some code
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 1) return 1;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        int result = 0;
        for (int n: dp){
            result = Math.max(result, n);
        }
        return result;
    }
}
```