LeetCode 300 - Longest Increasing Subsequence

作者 QIFAN 日期 2017-01-10
LeetCode 300 - Longest Increasing Subsequence

原题链接: 300. Longest Increasing Subsequence


题干

给定一个无序数组,求最长递增的长度,可以不连续。

举例
输入: [10, 9, 2, 5, 3, 7, 101, 18]
输出: 4
解释: 最长递增为 [2, 3, 7, 101][2, 5, 7, 18][2, 3, 7, 18] 最大长度为 4 。

要求:时间复杂度 $O(n^2)$

Follow up :
能不能用 $O(nlogn)$ ?

思路

使用简单粗暴的思路:

建立一个动态数组 dp ,dp[i] 表示以 nums[i] 为末尾的最大递增长度。对于 nums[i] ,往回查看 nums[j] (i > j >= 0)

case 1 : nums[i] > nums[j] ,max = max(max, dp[j] + 1)
case 2 : nums[i] ≤ nums[j] ,max = 1
res[i] = max

代码:

public int lengthOfLIS(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int[] res = new int[nums.length];
res[0] = 1;
int maxLength = Integer.MIN_VALUE;
for (int pos = 1; pos < nums.length; pos++) {
int subMaxLength = 0;
for (int subPos = pos - 1; subPos >= 0; subPos--) {
if (nums[subPos] < nums[pos]) {
subMaxLength = Math.max(subMaxLength, res[subPos]);
}
}
res[pos] = subMaxLength + 1;
maxLength = Math.max(maxLength, res[pos]);
}
return maxLength;
}

Follow up
Reference to :https://discuss.leetcode.com/topic/28719/short-java-solution-using-dp-o-n-log-n

看到 $O(nlogn)$ 应该想到的 binary search ,怎样可以让 dp 变成一个递增的数组呢?去看了 discussion ,思路差别在于 dp 的定义:

dp[i] is the minimum value a subsequence of length i+1 might end with

代码:

public class Solution {
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;
}
}