1ms consise java solution, o(n) space, but not sure what's the time complexity


  • 0
    S

    public class LongestIncreasingSubsequence {

    public int lengthOfLIS(int[] nums) {
    	int l = nums.length;
    	int[] inc = new int[l + 1];
    	inc[0] = Integer.MIN_VALUE;
    	int i = 0, j = 0, max = 0;
    	while (i < l) {
    		if (nums[i] > inc[max]) {
    			inc[++max] = nums[i++];
    			j = max;
    		} else {
    			while (inc[j] > nums[i])
    				--j;
    			inc[++j] = nums[i++];
    		}
    	}
    	return max;
    }
    

    }


Log in to reply
 

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