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 ^_^.


Log in to reply
 

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