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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 2500
	-104 &lt;= nums[i] &lt;= 104


&nbsp;
Follow up:&nbsp;Can you come up with an algorithm that runs in&nbsp;O(n log(n)) time complexity?

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:

        # Initialize the result
        res = []

        # Binary search to find the index of the smallest number in result that is greater than or equal to the target
        def binarySearch(l, r, target):

            nonlocal res

            # If the left and right pointers meet, we have found the smallest number that is greater than the target
            if l == r:
                return l

            # Find the mid pointer
            m = (r - l) // 2 + l

            # If the number at the mid pointer is equal to the target, we have found a number that is equal to the target
            if res[m] == target:
                return m

            # Else if the number at the mid poitner is less than the target, we search the right side
            elif res[m] < target:
                return binarySearch(m + 1, r, target)

            # Else, we search the left side including the number at mid pointer because it is one of the possible solution since it is greater than the target
            else:
                return binarySearch(l, m, target)

        # Iterate through all numbers
        for n in nums:

            # If the last number in the result is less than the current number
            if not res or res[-1] < n:

                # Append the current number to the result
                res.append(n)

                continue

            # Else, find the index of the smallest number in the result that is greater than or equal to the current number
            i = binarySearch(0, len(res) - 1, n)

            # Replace the current number at such index
            res[i] = n

        return len(res)
class Solution {
    public int lengthOfLIS(int[] nums) {

        ArrayList<Integer> lis = new ArrayList<>();

        for(int num:nums){

            int size = lis.size();

            if(size==0 ||size>0 && num>lis.get(size-1)){
                lis.add(num);
            }else{
                int insertIndex = bs(lis,num);
                lis.set(insertIndex,num);
            }
        }

        return lis.size();
    }

    int bs(List<Integer> list, int target){
        int lo = 0;
        int hi = list.size()-1;

        while(lo<hi){
            int mid = (lo+hi)/2;
            if(list.get(mid)<target){
                lo=mid+1;
            }else{
                hi=mid;
            }
        }
        return lo;
    }
}
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int>dp(n,1);
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(nums[j]>nums[i])dp[i]=max(dp[i],1+dp[j]);
            }
        }
       int mx=0;
       for(int i=0;i<n;i++)mx=max(mx,dp[i]);
       return mx;
    }
};
var lengthOfLIS = function(nums) {
  let len = nums.length;
  let dp = Array.from({length: len}, v => 1);
  
  for (let i = 1 ; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[i] <= dp[j]) {
        dp[i] = dp[j] + 1;
      }
    }
  }
  
  return Math.max(...dp);
};
Longest Increasing Subsequence