leetcode LongestIncreasingSubsequence

import java.util.Arrays;
import java.util.HashMap;

public class LongestIncreasingSubsequence {
  /**
   * Given an unsorted array of integers, find the length of longest increasing subsequence.
   *
   * Example:
   *
   * Input: [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.
   * Note:
   *
   * There may be more than one LIS combination, it is only necessary for you to return the length.
   * Your algorithm should run in O(n2) complexity.
   * Follow up: Could you improve it to O(n log n) time complexity?
   *
   * @param nums
   * @return
   */
  public int lengthOfLIS(int[] nums) {

    HashMap<Integer, Integer> m = new HashMap<>();

    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    int t = 0;

    for (int i = 0; i < n; i++) {
      int idx = binarySearch(dp, 0, i, nums[i]);
      dp[idx] = nums[i];
      if (idx == t) {
        t++;
      }
    }
    return t;
  }


  public int binarySearch(int[] nums, int left, int right, int target){
    while(left <= right){
      int mid = left + ((right - left) >> 1);
      if (nums[mid] == target) return mid;
      else if (nums[mid] > target) left = mid -1;
      else right = mid + 1;
    }
    return left;
  }
}