classSolution{publicintlengthOfLIS(int[] nums){int[] top =newint[nums.length];// 牌堆数初始化为 0int piles =0;for(int i =0; i < nums.length; i++){// 要处理的扑克牌int poker = nums[i];/***** 搜索左侧边界的二分查找 *****/int left =0, right = piles;while(left < right){int mid =(left + right)/2;if(top[mid]> poker){right = mid;}elseif(top[mid]< poker){left = mid +1;}else{right = mid;}}/*********************************/// 没找到合适的牌堆，新建一堆if(left == piles) piles++;// 把这张牌放到牌堆顶top[left]= poker;}// 牌堆数就是 LIS 长度return piles;}}
二、最长连续递增序列
classSolution{publicintfindLengthOfLCIS(int[] nums){int[] dp =newint[nums.length];for(int i =0; i < dp.length; i++){dp[i]=1;}int res =1;//可以注意到，這邊的 i 是從 0 開始，所以會出現和卡哥的C++ code有差異的地方，在一些地方會看到有 i + 1 的偏移。for(int i =0; i < nums.length -1; i++){if(nums[i +1]> nums[i]){dp[i +1]= dp[i]+1;}res = res > dp[i +1]? res : dp[i +1];}return res;}}
三、最长重复子数组
classSolution{publicintfindLength(int[]A,int[]B){int max =0;int[][] dp =newint[A.length +1][B.length +1];for(int i =1; i <=A.length; i++){for(int j =1; j <=B.length; j++){if(A[i -1]==B[j -1])dp[i][j]= dp[i -1][j -1]+1;elsedp[i][j]=0;max =Math.max(max, dp[i][j]);}}return max;}}
