leetcode-最长上升子序列LIS

转载原文地址：http://www.cnblogs.com/GodA/p/5180560.html

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

第一种方法：动态规划。

求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。

　　前1个数 d(1)=1 子序列为2；

　　前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7

　　前3个数在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1

　　前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5

　　前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6

　　前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4

　　前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3

　　前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8

　　前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9

　　d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5

　　总结一下，d(i)就是找以A[i]结尾的，在A[i]之前的最长上升子序列+1，当A[i]之前没有比A[i]更小的数时，d(i)=1。所有的d(i)里面最大的那个就是最长上升子序列。

public int longestIncreasingSubsequence(int[] nums) {

          if(nums.length==0)return 0;

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

        int max=0;

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

            d[i]=1;  //当nums[i]之前没有比nums[i]更小的数，d[i]=1.每次重新开始计数

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

                if(nums[j]<nums[i]&&(1+d[j]>d[i]))d[i]=1+d[j];//num[j]<num[i]保证了递增的操作，因此只需要不断比较并更新d[i]

            }

            if(d[i]>max)max=d[i];

        }

        return max;

    }

第二种方法：有以下序列A[]=3 1 2 6 4 5 10 7，求LIS长度。

核心思想是不断的替换，遍历nums数组，通知保证arr数组一定是一个递增的数组（因此可以使用二分法）

如果nums[i]比arr数组最右边的数字还要大，则将Nums[i]直接添加到arr数组的后边，否则nums[i]将会插入到arr[i]

中，使用二分查找法。

这里的二分查找是为了寻找第一个大于num[i]的数字。使用的是upper_bound。

如图所示

代码如下：

class Solution {

    public int lengthOfLIS(int[] nums) {

        if(nums.length==0)return 0;

        int max=0,next;

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

        arr[0]=nums[0];

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

            next=put(arr,0,max,nums[i]);    //从数组中的第二个数开始

            arr[next]=nums[i];

            if(max<next)max=next;

        }

        return max+1;

    }

    //找索引的方法，比如【2,1,4,5,3,6】找到nums[1]的索引为0，nums[2]=4直接添加到arr[2]中，nums[3]=5同理，nums[4]=3会把[1,4,5]中的4替换掉。

    public int put(int[] a,int l,int r,int key){

        if(a[r]<key)return r+1;

        int mid;

        while(l<=r){

            if(l==r)return l;

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

            //返回第一个大于key的索引

            if(a[mid]<key)l=mid+1;

            else r=mid;

        }

        return l;

    }

}

巴特西

leetcode-最长上升子序列LIS

最新文章

热门文章