C# O(nlogn) solution including a very helpful link

• As I stated in my previous post O(n^2 solution) , the fastest way is using an O(nlogn) algorithm for this problem.

I found this link very helpful and easy to understand. I strongly recommend to the people having difficulty in understanding the O(nlogn) approaches to LIS.

Here is the C# implementation (beats 85.22%)

``````public class Solution {
public int BinarySearchCeil(int[] a, int left, int right, int element){
while (right - left > 1){
int middle = (right + left) / 2;
if (a[middle] >= element)
right = middle;
else
left = middle;
}
return right;
}
public int LengthOfLIS(int[] nums) {
int n = nums.Length;
int len = 0;
if (n > 0){
len = 1;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; i++){
if (nums[i] < dp[0])
dp[0] = nums[i];
else if (nums[i] > dp[len - 1])
dp[len++] = nums[i];
else
dp[BinarySearchCeil(dp, -1, len - 1, nums[i])] = nums[i];
}
}
return len;
}
}
``````

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