# 300. Longest Increasing subsequence Leetcode Solution

## Longest Increasing subsequence Leetcode Problem :

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

## Longest Increasing subsequence Leetcode Solution :

### Constraints :

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

### 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.

Approach :

The main idea of this approach will be to find the longest common subsequence(LCS) between the given array and the sorted form of the array. However by careful observations (and a number of wrong submissions), it appears that duplicate elements play and important role too. We need to include duplicate elements once.

But, if we try to remove duplicasy in the given array, nums[], the order of the elements will be disturbed and we might get different results because the subsequence changes.

Therefore, we remove duplicasy in the sorted array. Finally, find the LCS between the given array and the sorted array(after duplicate elements are included only once).

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others