JAVA binary search solution with explanation


  • 1
    F

    In fact, this is a variant of the insert sort algorithm, we use binary search to find the insert point.
    The dp array is used to store the elements of the Longest Increasing Subsequence, of course, you can also use ArrayList to do the same job.

        public int lengthOfLIS(int[] nums) {
            /**
             * dp is used to store the elements of the Longest Increasing Subsequence
             */
            int[] dp = new int[nums.length];
            /**
             * initial length of the LIS
             */
            int len = 0;
            for (int num : nums) {
                /**
                 * search in a bounded array dp[0..len) to find the index of the
                 * insert point for the current num
                 */
                int idx = Arrays.binarySearch(dp, 0, len, num);
                /**
                 * if the element is not in the bounded array dp[0..len), then
                 * we get the index of the insert point using a conversion.
                 */
                if (idx < 0) {
                    idx = -idx - 1;
                }
                /**
                 * update the element
                 */
                dp[idx] = num;
                /**
                 * if the updated element is the last element, then the length of
                 * the LIS may be updated or not, but it is always equal to idx+1
                 */
                if (idx == len) {
                    len = idx + 1;
                }
            }
            return len;
        }

  • 0
    H

    I don't think we need the dp and dp is not the LIS.
    e.g. input = [1, 7, 8, 2], the LIS should be 1, 7, 8 while the result of dp is [1, 2, 8, 0]


  • 0
    F

    @houliang yes, you are right, but dp is still needed, can you solve the problem without dp


  • 0
    H

    @fhqplzj yes you are correct.


Log in to reply
 

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