# O(nlogn) solution in Java

• 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;
}
}
}
}``````

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