383940414243444546

import java.util.*;

class Solution {
    /* Function to find the longest increasing 
    subsequence in the given array */
    public int LIS(int[] nums) {
        int n = nums.length;
        
        List<Integer> temp = new ArrayList<>();
        temp.add(nums[0]);
        
        // Iterate on the elements of the array
        for (int i = 1; i < n; i++) {
            
            // If the current element can be added to the subsequence
            if (nums[i] > temp.get(temp.size() - 1)) 
                temp.add(nums[i]); 
                
            // Otherwise
            else {
                // Index at which the current element must be placed
                int ind = Collections.binarySearch(temp, nums[i]);
                if (ind < 0) ind = -(ind + 1);
                
                // Place the current element in the subsequence
                temp.set(ind, nums[i]);
            }    
        }
        
        // Return the length of temporary subsequence created so far
        return temp.size();
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        
        // Creating an object of Solution class
        Solution sol = new Solution();
        int lengthOfLIS = sol.LIS(nums);
        
        System.out.println("The length of the LIS for the given array is: " + lengthOfLIS);
    }
}

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647

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)

123456