Massive Algorithms: LeetCode 300 - Longest Increasing Subsequence

LeetCode 300 - Longest Increasing Subsequence

[LeetCode]Longest Increasing Subsequence | 书影博客
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n^2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

X. DP: O(N^2)

dp[x] = max(dp[x], dp[y] + 1) 其中 y < x

def lengthOfLIS(self, nums): size = len(nums) dp = [1] * size for x in range(size): for y in range(x): if nums[x] > nums[y]: dp[x] = max(dp[x], dp[y] + 1) return max(dp) if dp else 0
https://discuss.leetcode.com/topic/30721/my-easy-to-understand-o-n-2-solution-using-dp-with-video-explanation/6

public static int lengthOfLIS2(int[] nums) {
  if(nums.length == 0 || nums == null){
            return 0;
        }
        int []dp = new int[nums.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
                }
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }

http://www.jiuzhang.com/solutions/longest-increasing-subsequence/
http://www.cnblogs.com/lishiblog/p/4190936.html

 6     public int longestIncreasingSubsequence(int[] nums) {
 7         if (nums.length==0) return 0;
 8         int len = nums.length;
 9         int[] lisLen = new int[len];
10         lisLen[0] = 1;
11         int maxLen = lisLen[0];
12         for (int i=1;i<len;i++){
13             lisLen[i]=1; //\\
14             for (int j=i-1;j>=0;j--)
15                 if (nums[i]>=nums[j] && lisLen[i]<lisLen[j]+1)
16                     lisLen[i] = lisLen[j]+1;
17             if (maxLen<lisLen[i]) maxLen = lisLen[i];
18         }
20         return maxLen;
22     }

http://buttercola.blogspot.com/2015/12/leetcode-longest-increasing-subsequence.html

    public int lengthOfLIS(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

}

        int[] dp = new int[nums.length + 1];

        for (int i = 1; i < nums.length + 1; i++) {

            dp[i] = 1;

}

        int maxLen = 1;

        for (int i = 1; i <= nums.length; i++) {

            for (int j = 1; j < i; j++) {

                if (nums[i - 1] > nums[j - 1]) {

                    dp[i] = Math.max(dp[i], dp[j] + 1);

}

}

            maxLen = Math.max(maxLen, dp[i]);

}

        return maxLen;

}

https://discuss.leetcode.com/topic/28719/short-java-solution-using-dp-o-n-log-n/3

    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }

public int lengthOfLIS(int[] nums) {
    ArrayList<Integer> dp = new ArrayList<>(nums.length);
    for (int num : nums) {
        if (dp.size() == 0 || dp.get(dp.size()-1) < num) dp.add(num);
        else {
            int i = Collections.binarySearch(dp, num);
            dp.set((i<0) ? -i-1 : i, num);
        }
    }
    return dp.size();
}

X. O(n * log n)解法: 维护一个单调序列

// 有贪心选择的意思

public int lengthOfLIS(int[] nums) {

int len = nums.length;

// 先考虑极端输入

if (len <= 1) {

return len;

}

// tail 数组的定义：长度为 i+1 的上升子序列的末尾最小是几

int[] tail = new int[len];

// 遍历一遍整个数组，使用二分查找算法

tail[0] = nums[0];

int res = 0;

for (int i = 1; i < len; i++) {

// 比 tail 数组实际有效的末尾的那个元素还大

if (nums[i] > tail[res]) {

// 直接添加在那个元素的后面

tail[++res] = nums[i];

} else {

// 二分查找到第 1 个比 nums[i] 还大的元素，更新到那个位置

int l = 0;

int r = res;

while (l < r) {

int mid = l + (r - l) / 2;

// 有就啥都不做了

if (tail[mid] == nums[i]) {

l = mid;

break;

} else if (tail[mid] >= nums[i]) {

r = mid;

} else {

l = mid + 1;

}

tail[l] = nums[i];

}

printArray(nums[i], tail);

}

return ++res;

}

https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation

tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i].
For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
len = 3   :      [4, 5, 6]            => tails[2] = 6

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]

Doing so will maintain the tails invariant. The the final answer is just the size

https://leetcode.com/articles/longest-increasing-subsequence/
Approach #4 Dynamic Programming with Binary Search

In this approach, we scan the array from left to right. We also make use of a

dp

array initialized with all 0's. This

dp

array is meant to store the increasing subsequence formed by including the currently encountered element. While traversing the

nums

array, we keep on filling the

dp

array with the elements encountered so far. For the element corresponding to the

j^{th}

index (

nums[j]

), we determine its correct position in the

dp

array(say

i^{th}

index) by making use of Binary Search(which can be used since the

dp

array is storing increasing subsequence) and also insert it at the correct position. An important point to be noted is that for Binary Search, we consider only that portion of the

dp

array in which we have made the updates by inserting some elements at their correct positions(which remains always sorted). Thus, only the elements upto the

i^{th}

index in the

dp

array can determine the position of the current element in it. Since, the element enters its correct position(

i

) in an ascending order in the

dp

array, the subsequence formed so far in it is surely an increasing subsequence. Whenever this position index

i

becomes equal to the length of the LIS formed so far(

len

), it means, we need to update the

len

len = len + 1

Note:

dp

array does not result in longest increasing subsequence, but length of

dp

array will give you length of LIS.

Consider the example:

input: [0, 8, 4, 12, 2]

dp: [0]

dp: [0, 8]

dp: [0, 4]

dp: [0, 4, 12]

dp: [0 , 2, 12] which is not the longest increasing subsequence, but length of

dp

array results in length of Longest Increasing Subsequence.

Note: Arrays.binarySearch() method returns index of the search key, if it is contained in the array, else it returns (-(insertion point) - 1). The insertion point is the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key.

Complexity Analysis

Time complexity : $O(nlog(n))$ . Binary search takes $log(n)$ time and it is called $n$ times.
Space complexity : $O(n)$ . $dp$ array of size $n$ is used.

public int lengthOfLIS(int[] nums) {

int[] dp = new int[nums.length];

int len = 0;

for (int num : nums) {

int i = Arrays.binarySearch(dp, 0, len, num);

if (i < 0) {

i = -(i + 1);

}

dp[i] = num;

if (i == len) {

len++;

}

return len;

}

http://blog.welkinlan.com/2015/11/05/longest-increasing-subsequence-leetcode-java/
Maintain a potential LIS arraylist
for each element n, append it to the tail of LIS if its the largest O/W binary search the insert position in the LIS, then replace the original element with n.

https://leetcode.com/discuss/67609/short-java-solution-using-dp-o-n-log-n

The idea is that as you iterate the sequence, you keep track of the minimum value a subsequence of given length might end with, for all so far possible subsequence lengths. So dp[i] is the minimum value a subsequence of length i+1 might end with. Having this info, for each new number we iterate to, we can determine the longest subsequence where it can be appended using binary search. The final answer is the length of the longest subsequence we found so far.

Arrays.binarySearch() returns ( - insertion_index - 1) in cases where the element was not found in the array. Initially the dp array is all zeroes. For all zeroes array the insertion index for any element greater than zero is equal to the length of the array (dp.length in this case). This means that the number needs to be added to the end of the array to keep the array sorted.

As a result pos is equal to insertion_index, which is equal to dp.length. So the dp[pos] = nums[i]; line fails, because pos is out of bounds.

This problem does not happen when searching just part of the array by using Arrays.binarySearch(dp, 0, len, nums[i]), because in this case the insertion index is len.

By the way the issue will happen on any input that contains a positive integer, e.g. [1].

    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }

public int lengthOfLIS(int[] nums) {
    ArrayList<Integer> dp = new ArrayList<>(nums.length);
    for (int num : nums) {
        if (dp.size() == 0 || dp.get(dp.size()-1) < num) dp.add(num);
        else {
            int i = Collections.binarySearch(dp, num);
            dp.set((i<0) ? -i-1 : i, num);//\\
        }
    }
    return dp.size();
}

This is a great solution. By the way, what is the difference between two versions of Arrays.binarySearch()? If substitute it with another one, it has the error: java.lang.ArrayIndexOutOfBoundsException: 8 for input [10,9,2,5,3,7,101,18]... Has anyone seen where the problem is?

    public int lengthOfLIS(int[] nums) {
        // keep track of the end elements of each lists
        int[] dp = new int[nums.length];
        int len = 0;
        for(int i = 0; i<nums.length; i++){
            int pos = Arrays.binarySearch(dp,nums[i]);
            if(pos < 0){
               pos = - pos - 1;
            }
            dp[pos] = nums[i];
            if(pos == len) len++;
        }
        return len;
    }

    public int lengthOfLIS(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

}

        ArrayList<Integer> lis = new ArrayList<Integer>();

        for (int n : nums) {

            if (lis.size() == 0 || lis.get(lis.size() - 1) < n) {

                lis.add(n);

            } else {

                updateLIS(lis, n);

}

}

        return lis.size();

}

    private void updateLIS(ArrayList<Integer> lis, int n) {

        int l = 0, r = lis.size() - 1;

        while (l < r) {

            int m = l + (r - l) / 2;

            if (lis.get(m) < n) {

                l = m + 1;

            } else {

                r = m;

}

}

        lis.set(l, n);

}

https://leetcode.com/discuss/67565/simple-java-o-nlogn-solution
https://leetcode.com/discuss/74510/java-easy-version-to-understand
public int lengthOfLIS(int[] nums) { List<Integer> sequence = new ArrayList(); for(int n : nums) update(sequence, n); return sequence.size(); } private void update(List<Integer> seq, int n) { if(seq.isEmpty() || seq.get(seq.size() - 1) < n) seq.add(n); else { seq.set(findFirstLargeEqual(seq, n), n); } } private int findFirstLargeEqual(List<Integer> seq, int target) { int lo = 0; int hi = seq.size() - 1; while(lo < hi) { int mid = lo + (hi - lo) / 2; if(seq.get(mid) < target) lo = mid + 1; else hi = mid; } return lo; }

遍历nums数组，二分查找每一个数在单调序列中的位置，然后替换之。
def lengthOfLIS(self, nums): size = len(nums) dp = [] for x in range(size): low, high = 0, len(dp) - 1 while low <= high: mid = (low + high) / 2 if dp[mid] >= nums[x]: high = mid - 1 else: low = mid + 1 if low >= len(dp): dp.append(nums[x]) else: dp[low] = nums[x] return len(dp)
https://leetcode.com/discuss/67625/java-simple-and-easy-understanding-nlogn-solution

http://blog.csdn.net/u014688145/article/details/69663661
官网给出了两种解法，时间复杂度分别为

O(n2)和

O(nlogn).
如果我们用dp表示的话，dp[i] = Math.max(dp[i],dp[j]+1)
public int lengthOfLIS(int[] nums) { if (nums.length == 0) return 0; int[] dp = new int[nums.length+1]; int max = 0; for (int i = 0; i < nums.length; i++){ dp[i] = 1; for (int j = 0; j < i; j ++){ if (nums[i] > nums[j]){ dp[i] = Math.max(dp[i], dp[j]+1); } } max = Math.max(max, dp[i]); } return max; }

注意if条件的判断，只有当满足数组元素递增情况下，我才更新dp，很容易理解。max只需要随着dp[i]更新就好了。

官网还提出提示了另外一种更高效的算法，它的时间复杂度为

O(nlogn)，那么它应该怎么做？其实，在上述做法当中，你能看到一些瑕疵，它的第一层循环是定位当前i元素，并与前i-1个元素比较，这有点像插入排序，而我们知道插入排序在定位到第i个元素时，前面的元素已经是有序的了，有一种做法可以加快我们的查找速度，二分！！！而像第一种解法，虽然做了同样的

O(n2)次的比较，但它没有更新元素的顺序，所以它所隐含的有序状态并没有得到高效利用。

所以自然而然的想法就出来了，我们每当定位到当前元素时，就把当前元素放到它该去的位置，如[10,9]比较后，显然应该变成[9,10]，但这种状态由题目意思是非法的，所以砍掉[10],就有了[9]，而此时定位到2，又更新为[2],继续i定位到5时，变成了[2,5]，这种状态是合法的，所以有了最新最长递增序列，它的好处就很明显了，本身有序，所以当前元素i在搜索位置插入时，可以优化到

logn，接下来就重点关注如何二分了！

该问题就变成了，只有【后续的元素大于当前最后一个元素】时，就增加数组长度并插入到最后位置。其它的，当小于等于最后一个元素时快速定位到指定位置即可。我们只要抓住括号内这个关键点即可。

抽象一下，我们只需要找到最大的下标i,使得dp[i] < key即可，所以有如下代码：

public int lengthOfLIS(int[] nums) { if(nums.length == 0) return 0; int[] dp = new int[nums.length]; int len = 1; dp[0] = nums[0]; for (int i = 1; i < nums.length; i++){ int index = binarySearch(dp, 0, len-1, nums[i]); dp[index + 1] = nums[i]; if (index + 1 == len){ len ++; } } return len; } //典型的一种二叉树应用，保证它的准确性 private int binarySearch(int[] nums, int lf, int rt, int key){ while (lf < rt){ int mid = lf + (rt + 1 - lf) / 2; if(nums[mid] >= key){ rt = mid - 1; }else{ lf = mid; } } if (nums[lf] < key) return lf; return -1; }

可以去调试它去理解它的过程，这里总结两点：

当前i元素，插入到[0,len-2]的位置上，你可以丢弃它不看。
当前i元素，插入到 len - 1 的位置上时，它是你当前最长递增子序列中的一个解。
当前i元素，插入到 len 的位置上时，长度被更新，可见 len - 1 位置上元素的重要性。

X, Brute Force
https://leetcode.com/articles/longest-increasing-subsequence/

Time complexity : $O(2^n)$ . Size of recursion tree will be $2^n$ .
Space complexity : $O(n^2)$ . $memo$ array of size $n * n$ is used.

The simplest approach is to try to find all increasing subsequences and then returning the maximum length of longest increasing subsequence. In order to do this, we make use of a recursive function

lengthofLIS

which returns the length of the LIS possible from the current element(corresponding to

curpos

) onwards(including the current element). Inside each function call, we consider two cases:

The current element is larger than the previous element included in the LIS. In this case, we can include the current element in the LIS. Thus, we find out the length of the LIS obtained by including it. Further, we also find out the length of LIS possible by not including the current element in the LIS. The value returned by the current function call is, thus, the maximum out of the two lengths.
The current element is smaller than the previous element included in the LIS. In this case, we can't include the current element in the LIS. Thus, we find out only the length of the LIS possible by not including the current element in the LIS, which is returned by the current function call.

public int lengthOfLIS(int[] nums) {

return lengthofLIS(nums, Integer.MIN_VALUE, 0);

}

public int lengthofLIS(int[] nums, int prev, int curpos) {

if (curpos == nums.length) {

return 0;

}

int taken = 0;

if (nums[curpos] > prev) {

taken = 1 + lengthofLIS(nums, nums[curpos], curpos + 1);

}

int nottaken = lengthofLIS(nums, prev, curpos + 1);

return Math.max(taken, nottaken);

}

Approach #2 Recursion with memorization [Memory Limit Exceeded]

Time complexity : $O(n^2)$ . Size of recursion tree can go upto $n^2$ .
Space complexity : $O(n^2)$ . $memo$ array of $n*n$ is used.

public int lengthOfLIS(int[] nums) {

int memo[][] = new int[nums.length + 1][nums.length];

for (int[] l : memo) {

Arrays.fill(l, -1);

}

return lengthofLIS(nums, -1, 0, memo);

}

public int lengthofLIS(int[] nums, int previndex, int curpos, int[][] memo) {

if (curpos == nums.length) {

return 0;

}

if (memo[previndex + 1][curpos] >= 0) {

return memo[previndex + 1][curpos];

}

int taken = 0;

if (previndex < 0 || nums[curpos] > nums[previndex]) {

taken = 1 + lengthofLIS(nums, curpos, curpos + 1, memo);

}

int nottaken = lengthofLIS(nums, previndex, curpos + 1, memo);

memo[previndex + 1][curpos] = Math.max(taken, nottaken);

return memo[previndex + 1][curpos];

}

Read full article from [LeetCode]Longest Increasing Subsequence | 书影博客

LeetCode 300 - Longest Increasing Subsequence

Labels

Popular Posts