# 300. Longest Increasing Subsequence

```java
class Solution {
    public int lengthOfLIS(int[] nums) {
        // j in the range of[0, i-1];
        // define dp[i] as the lenth of the LIS that end at index i;
        // dp[i]= max(dp[j]+1,1);
        int len = nums.length;
        int[] memo = new int[len];
        int ans = 0;
        for (int i=0; i<len; i++){
            memo[i]=1;
            for(int j=0; j<i; j++){
                if(nums[i]>nums[j]) memo[i] = Math.max(memo[j]+1, memo[i]);
            }
            ans = Math.max(ans, memo[i]);
        }
        return ans;
    }
}
```
