JAVA--------------Easy Version To Understand!!!!!!!!


  • 27
    H
    public static int findPositionToReplace(int[] a, int low, int high, int x) {
    	int mid;
    	while (low <= high) {
    		mid = low + (high - low) / 2;
    		if (a[mid] == x)
    			return mid;
    		else if (a[mid] > x)
    			high = mid - 1;
    		else
    			low = mid + 1;
    	}
    	return low;
    }
    
    public static int lengthOfLIS(int[] nums) {
    	if (nums == null | nums.length == 0)
    		return 0;
    	int n = nums.length, len = 0;
    	int[] increasingSequence = new int[n];
    	increasingSequence[len++] = nums[0];
    	for (int i = 1; i < n; i++) {
    		if (nums[i] > increasingSequence[len - 1])
    			increasingSequence[len++] = nums[i];
    		else {
    			int position = findPositionToReplace(increasingSequence, 0, len - 1, nums[i]);
    			increasingSequence[position] = nums[i];
    		}
    	}
    	return len;
    }

  • 0
    D

    I think your code will not return right value for this input. arr = [3,5,6,2,5,4,19,5,6,7,12]


  • 0
    H

    you are wrong,please read my code carefully.


  • 0
    D

    Yup. I am sorry. I used strictly > for the Binary search whereas you used >=. That did the all difference.


  • 0
    V

    How does it work for an example like :[10, 12, 13, 4, 5] ? It seems like the increasingSequence will be [4, 5, 13] --> the length will be correct, but the actual increasingSequence is incorrect. Please correct me if I'm wrong


  • 0
    P

    yes, you are right, but it doesn't matter.


  • 0
    P

    nice and clear


  • 0
    E

    Very self-explanatory code! The coding style is very similar to mine ^_^.


  • 0
    J

    May I ask why we return low in the binary search here? Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.