O(nlogn) solution in Java


  • 0
    W

    You can find the basic idea in wikipedia: https://en.wikipedia.org/wiki/Longest_increasing_subsequence
    public class Solution {
    public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
    return 0;
    }
    if (nums.length == 1) {
    return 1;
    }

        int[] increasing = new int[nums.length];
        increasing[0] = 0;
        int len = 1;
        
        int[] last = new int[nums.length];
        last[0] = -1;
        
        for (int i = 1; i < nums.length; i++) {
            int pos = getPos(nums, increasing, len, nums[i]);
            len = Math.max(len, pos+1);
            
            last[i] = pos == 0 ? -1 : increasing[pos-1];
            increasing[pos] = i;
        }
        
        return len;
    }
    
    private int getPos (int[] nums, int[] increasing, int len, int num) {
        if (num > nums[increasing[len-1]]) {
            return len;
        } else {
            int l = 0, r = len-1;
            
            while (l + 1 < r) {
                int m = l + (r-l)/2;
                
                if (nums[increasing[m]] == num) {
                    l = m+1;
                } else if (nums[increasing[m]] < num) {
                    l = m+1;
                } else {
                    r = m;
                }
            }
            
            if (num < nums[increasing[l]]) {
                return l;
            } else {
                return r;
            }
        }
    }
    }

Log in to reply
 

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