转载原文地址：http://www.cnblogs.com/GodA/p/5180560.html
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入:[10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是[2,3,7,101]，它的长度是4。
说明:
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
第一种方法：动态规划。
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长度。
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; } }
原文：https://www.cnblogs.com/patatoforsyj/p/9638521.html