LeetCode - Algorithms - 300. Longest Increasing Subsequence

Longest increasing subsequence 看来也是道比较经典的算法题，LeetCode 与 LintCode 都有此题。

有名的算法网站 Rosetta Code 上有此题的N种语言之实现 Longest increasing subsequence

Dynamic Programming

琢磨不出来，上网搜罗

google关键字:

  • longest increasing subsequence dynamic programming
  • longest increasing subsequence optimal substructure

这是相关资料：

代码虽然在LeetCode上跑通了，但还是没有完全理解其中的步骤，还是处于知其然而不知其所以然的阶段，好像有点数学归纳法的意味，也有点像递归，动态规划好像也能用来解决兔子序列问题。

java

Efficient algorithms followed Wikipedia

binary search + DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int lengthOfLIS(int[] nums) {
		int N = nums.length;
		int[] M = new int[N + 1];

		int L = 0;
		for (int i = 0; i < N; i++) {
			int lo = 1;
			int hi = L;
			while (lo <= hi) {
				int mid = new Double(Math.ceil((lo + hi) / 2)).intValue();
				if (nums[M[mid]] < nums[i])
					lo = mid + 1;
				else
					hi = mid - 1;
			}

			int newL = lo;

			M[newL] = i;

			if (newL > L)
				L = newL;
		}
		return L;        
    }
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 5 ms, faster than 75.39% of Java online submissions for Longest Increasing Subsequence.
  • Memory Usage: 39.2 MB, less than 12.91% of Java online submissions for Longest Increasing Subsequence.

o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLIS(int[] nums) {
    	if (nums.length==0)
    		return 0;
    	int[] L = new int[nums.length];
    	L[0]=1;
    	for(int i=1;i<nums.length;i++) {
    		for(int j=0;j<i;j++) {
    			if(nums[j]<nums[i] && L[j]>L[i])
    				L[i] = L[j];
    		}
    		L[i]++;
    	}
    	return Arrays.stream(L).max().getAsInt();        
    }
}

Submission Detail

  • 24 / 24 test cases passed.
  • Your runtime beats 5.56 % of java submissions.

javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
  if (nums==null || nums.length==0)
      return 0;
  var arr = new Array(nums.length);
  for(i=0;i<arr.length;i++)
    arr[i] = 0;
	arr[0] = 1;
  for(i=1;i<nums.length;i++) {
    for(j=0;j<i;j++) {
	  if (nums[j]<nums[i] && arr[j]>arr[i]) {
	    arr[i] = arr[j];
	  }
	}
	arr[i]++;
  }
  var maxLISLen = arr[0];
  for(var i=1;i<arr.length;i++) {
    if (arr[i]>maxLISLen)
	  maxLISLen = arr[i];
  }
  return maxLISLen;    
};

Submission Detail

  • 24 / 24 test cases passed.
  • Your runtime beats 13.56 % of javascript submissions.

此题使用动态规划的算法看来性能不好，时间复杂度为O(n2)，维基百科上说最有效的算法为 Patience sorting，能达到 O(n log n)