> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-lis/300.-longest-increasing-subsequence.md).

# 300. Longest Increasing Subsequence

## Problem Statement

<br>

Given an integer array `nums`, return *the length of the longest **strictly increasing***&#x20;

***subsequence***.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [10,9,2,5,3,7,101,18]
</strong><strong>Output: 4
</strong><strong>Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [0,1,0,3,2,3]
</strong><strong>Output: 4
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [7,7,7,7,7,7,7]
</strong><strong>Output: 1
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 2500`
* `-104 <= nums[i] <= 104`\ <br>

## Intuition

```
Maintain state of index, Prev  , 
This tells the lenght of LIS at index with some prev

```

### Links

<https://leetcode.com/problems/longest-increasing-subsequence/description/>

### Video Links

<https://www.youtube.com/watch?v=ekcwMsSIzVc&ab_channel=takeUforward>\
\
<https://www.youtube.com/watch?v=IFfYfonAFGc&ab_channel=takeUforward>

### Approach 1:

```
Memoization
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int find_ans(vector<int>& nums, int index, int prev, vector<vector<int>> &dp){
        if(index<0)
            return 0;

        if(dp[index][prev] != -1)
            return dp[index][prev];

        int not_take = find_ans(nums, index-1, prev, dp);
        
        int take = 0;
        if(prev == nums.size() or nums[index] < nums[prev]){
            take = 1 + find_ans(nums, index-1, index, dp);
        }

        return dp[index][prev] = max(take, not_take);
    }

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int prev = -1;
        vector<vector<int>> dp(n, vector<int>(n+1,-1));

        return find_ans(nums, n-1, n, dp);
    }
};
```

{% endcode %}

### Approach 2:

```
New Solution: 

dp[i] represnts longest LIS count until index i

Go N^2 and check for all prevs before and add if less

Refer Stiver Video for more clarity
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int lengthOfLIS(vector<int>& arr) {
        int n = arr.size();
        vector<int> dp(n, 1);
        int maxi = 1;

        for(int index=0; index<n; index++){
            for(int prev=0; prev<index; prev++){
                if(arr[prev] < arr[index]){
                    dp[index] = max (1+dp[prev], dp[index]);
                }
            }
            maxi = max(maxi, dp[index]);
        }

        return maxi;
    }
};
```

{% endcode %}

### Approach 3:

```
Printing LIS

Slight modification to above code

Maintain hash containing info for backtracking
Basically, 
When you get updation in dp array, means you got big LIS
Update in hash array as the index which gave that updation 

So that when you finish, You will have a lastindex, 
with which you can backtrack till the end
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int lengthOfLIS(vector<int>& arr) {
        int n = arr.size();
        vector<int> dp(n, 1), hash(n);
        int maxi = 1;
        int last_index = 0;

        for(int index=0; index<n; index++){
            hash[index] = index;
            for(int prev=0; prev<index; prev++){

                if(arr[prev] < arr[index] and 1+dp[prev] > dp[index]){
                    dp[index] = 1+dp[prev];
                    hash[index] = prev;
                }
            }

            if(dp[index] > maxi){
                maxi = dp[index];
                last_index = index;
            }
        }

        vector<int> ans;
        ans.push_back(arr[last_index]);

        while(hash[last_index] != last_index){
            last_index = hash[last_index];
            ans.push_back(arr[last_index]);
        }

        reverse(ans.begin(), ans.end());

        for(auto &it: ans)
            cout<<it<<" ";


        return maxi;
    }
};
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###