Longest Increasing Subsequence

发表于

Longest Increasing Subsequence

Question

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.

Analysis

  • Java Arrays.binarySearch 在调用前需要对数组进行排序，否则返回的下角标不定。在找到相应元素的时候，返回相应的下标（从0开始）；若未找到相应的元素，返回数值应插入的位置的负值（从1开始）。

    Java Array.binarySearch 用法总结

  1. 基本解法：

    ​ 数组dp记录以当前数字num[i]结尾的最长递增序列的长度，所以针对于dp[i+1]需要遍历0-i的内容，判断当前数字num[i+1]>num[j]是否成立，假如成立且dp[j]+1>dp[i+1]，则更新。

    • 在更新的过程中需要利用max记录最大长度
    • 在进行填充之前，需要将数组dp所有元素均赋值为1

  2. 优化解法：

    参考题解

    ​ 优化解法利用二分搜索来保证当前最长序列中的每个元素都是遍历数字中的最小的那个，只有在当前元素num[i]大于dp中的最大元素的时候，才会延长最长序列的长度。而该条件即len==i（len虽然代表最大的串长度，但是脚标从0开始，所以len也是下一个期望插入数字的位置）。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0)  return 0;
        int len=nums.length;
        int[] dp=new int[len];
        Arrays.fill(dp,1);
        int max=1;
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]&&dp[j]+1>dp[i])
                    dp[i]=dp[j]+1;
            }
            max=Math.max(dp[i],max);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int max=0;
        int[] dp=new int[nums.length];
        for(int tmp:nums){
            int i=Arrays.binarySearch(dp,0,max,tmp);
            if(i<0) i=-(i+1);
            dp[i]=tmp;
            if(i==max)  max++;
        }
        return max;
    }
}