# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-lis/300.-longest-increasing-subsequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.