Search

# Longest Increasing Subsequence

Updated: Mar 25, 2021

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

```Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

```

Example 2:

```Input: nums = [0,1,0,3,2,3]
Output: 4

```

Example 3:

```Input: nums = [7,7,7,7,7,7,7]
Output: 1

```

Constraints:

• 1 <= nums.length <= 2500

• -104 <= nums[i] <= 104

Solution:

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