4041424344454647

class Solution:
    # Function to find the longest increasing 
    # subsequence in the given array
    def LIS(self, nums):
        n = len(nums)
        
        temp = []
        temp.append(nums[0])
        
        # Iterate on the elements of the array
        for i in range(1, n):
            
            # If the current element can be added to the subsequence
            if nums[i] > temp[-1]:
                temp.append(nums[i]) 
            
            # Otherwise
            else:
                # Index at which the current element must be placed
                ind = self.lower_bound(temp, nums[i])
                
                # Place the current element in the subsequence
                temp[ind] = nums[i]
        
        # Return the length of temporary subsequence created so far
        return len(temp)

    # Binary search to find the index of the smallest element >= target
    def lower_bound(self, temp, target):
        left, right = 0, len(temp) - 1
        while left <= right:
            mid = (left + right) // 2
            if temp[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

# Example usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]

# Creating an object of Solution class
sol = Solution()
lengthOfLIS = sol.LIS(nums)

print("The length of the LIS for the given array is:", lengthOfLIS)

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253

class Solution {
    /* Function to find the longest increasing 
    subsequence in the given array */
    LIS(nums) {
        let n = nums.length;
        
        let temp = [];
        temp.push(nums[0]);
        
        // Iterate on the elements of the array
        for (let i = 1; i < n; i++) {
            
            // If the current element can be added to the subsequence
            if (nums[i] > temp[temp.length - 1]) 
                temp.push(nums[i]); 
                
            // Otherwise
            else {
                // Index at which the current element must be placed
                let ind = this.lowerBound(temp, nums[i]);
                
                // Place the current element in the subsequence
                temp[ind] = nums[i];
            }    
        }
        
        // Return the length of temporary subsequence created so far
        return temp.length;
    }
    
    // Binary search to find the index of the smallest element >= target
    lowerBound(temp, target) {
        let left = 0, right = temp.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (temp[mid] < target) 
                left = mid + 1;
            else 
                right = mid - 1;
        }
        return left;
    }
}

// Example usage
let nums = [10, 9, 2, 5, 3, 7, 101, 18];

// Creating an object of Solution class
let sol = new Solution();
let lengthOfLIS = sol.LIS(nums);

console.log("The l