面试热题（最长上升子序列）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

       由上图我们可以很容易直到该数组中的最长递增子序列的长度为4，可是计算机可不知道这么算，所以我们要告诉它得这么算，我们仔细找找规律

       这种的分析是不是能让你看出一点点规律，如果当前值i比i-1前的最长自序列的最后一个值大时，将当前这个值加入这个递增子序列中，是不是我们就比较容易得到：

        for (int i = 1; i <nums.length; i++) {for (int j = 0; j <i; j++) {if(nums[j]<nums[i]){dp[i]=Math.max(dp[j]+1,dp[i]); }}}

       那么我们动态规划中最难的一步已经写出来了，状态转移方程，接下来就是动规的一般解题步骤，入参判断，维护一个dp数组，对其进行初始化，具体的看下面的源代码：

 public int lengthOfLIS(int[] nums) {if(nums==null||nums.length==0){return 0;}int[] dp=new int[nums.length];Arrays.fill(dp,1);for (int i = 1; i <nums.length; i++) {for (int j = 0; j <i; j++) {if(nums[j]<nums[i]){dp[i]=Math.max(dp[j]+1,dp[i]); }}}return Arrays.stream(dp).max().getAsInt();}

       在大家再给大家介绍一种解法，面试时两种解法任选一种即可，我认为还是动态规划这种比较容易好记

堆纸牌方法：

这种方法一般人还真想不到，可能那种久经牌场的人说不定可以想到：

       类似于蜘蛛纸牌一样的游戏规则，每次找到最左边的适合当前牌的牌堆，如果没有就直接新创一个牌堆

 没堆牌出一张组成子序列，牌堆的堆数越多，最长子序列的长度也就越大：

【5，6，7，J】、【5，7，8，J】...

所以我们应该怎么样去模拟这个算法呢？

由于我们要时刻的知道每堆牌的顶牌，所以我们可以维护一个数组去记录每个堆的牌顶

int[] top=new int[nums.length];
int count=0;//一开始，未进行发牌，牌堆数为0

 如果有这么sexy的荷官给你发牌，你做题怎么可能会错？比如邱淑贞姐姐给你发牌，哒哒哒...

       因为数组中的索引是从0开始的，但是牌堆数确实从1开始的，所以当我们查找可以放当前牌的最左牌堆的索引等于牌堆数的时候，就应该重新创建一个牌堆，如果不太了解二分搜索最左侧搜索，请看二分搜索篇

    public int lengthOfLIS(int[] nums) {if(nums==null||nums.length==0){return 0;}int[] top=new int[nums.length];int count=0;//进行发牌for(int num:nums){int left=0;int right=count;//这里给大家说明以下，这种二分查找区间的时候区间是左闭右开的//因为count代表的是堆数(从1开始)，但是right指针代表的是数组的索引(从0开始)，指针永远不可能到达堆数的数量while(left<right){int mid=left+(right-left)/2;if(top[mid]>=num){right=mid;//不断的去优先收缩右区间}else{left=mid+1;//收缩左区间}}//找到最小的大于等于num的索引大小if(left==count){count++;}//更新牌顶元素top[left]=num;}return count;}