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


  • 0
    K

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

Log in to reply
 

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