`dp[i]`

represents the the length of the LIS till `nums[i]`

.

For each `nums[i]`

, we need to compare all the `nums[j]`

where `0`

<= `j`

< `i`

, if `nums[i]`

> `nums[j]`

, then `dp[i]`

= `dp[j]`

+ `1`

, that means we have found a potential LIS.

Let `i`

go through the `nums[]`

array, eventually we will get the longest length of LIS.

Time complexity is `O(n^2)`

.

```
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int n = nums.length, max = 0;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
max = Math.max(max, dp[i]);
}
return max;
}
```