Optimizing Code for Longest Increasing Subsequence in C++: Explained w

Hey, so today we are going to solve Leetcode - Longest Increasing Subsequence

Problem Link- https://leetcode.com/problems/longest-increasing-subsequence

class Solution {
public:
       int lengthOfLIS(vector<int>& nums) {
         vector<int> res;

         for(int i =0; i<nums.size(); i++){
         auto it = lower_bound(res.begin(), res.end(), nums[i]);
         if(it == nums.end()){
         res.emplace_back(nums[i]); 
         } 
         else {
         *it = nums[i]; 
         }
        }

        return res.size();
        }

}

The class Solution contains a member function lengthOfLIS that takes a vector nums as input and returns an integer representing the length of the Longest Increasing Subsequence (LIS) within the vector.
Inside the function, a vector res is declared, which will store the LIS elements.
A loop is used to iterate through each element of the nums vector.
For each element, std::lower_bound is used to find the position where the element can be inserted in the res vector while maintaining the increasing order.
If the iterator it points to the end of the res vector, it means that the current element is greater than all the elements in res. In this case, the current element is appended to the end of res.
If the iterator it points to a valid position within the res vector, it means that the current element can replace an existing element and still maintain the increasing order. Therefore, the element at position it is updated with the current element.
After iterating through all the elements of nums, the length of the LIS is equal to the size of the res vector.

Now, let's visualize the code using an example:

nums: [10, 9, 2, 5, 3, 7, 101, 18]

Initially, the res vector is empty.

Step 1:

Current element: 10
res: [10]

Step 2:

Current element: 9
res: [9]

Step 3:

Current element: 2
res: [2]

Step 4:

Current element: 5
res: [2, 5]

Step 5:

Current element: 3
res: [2, 3]

Step 6:

Current element: 7
res: [2, 3, 7]

Step 7:

Current element: 101
res: [2, 3, 7, 101]

Step 8:

Current element: 18
res: [2, 3, 7, 18]

Finally, the function returns the size of the res vector, which is 4, representing the length of the Longest Increasing Subsequence in the given vector nums.

DSA - Longest Increasing Subsequence - C++,Dynamic Programming