300. Longest Increasing Subsequence

Problem Statement

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

subsequence.

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

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

C++

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);
    }
};

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

C++

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;
    }
};

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

C++

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;
    }
};

Approach 4:

C++

Similar Problems