day105（3.6）——leetcode面试经典150

300. 最长递增子序列

300. 最长递增子序列

今天坐了一天车，终于到学校了，太不容易了，然后一直坐车也没来得及吃饭，回来了就大吃特吃，结果吃撑了，十一点多才忙完，加油！！！明天收拾完东西就出发学习！！！

题目：

题解：

class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; //dp数组表示到第k位是最多能有几个递增序列数 int[] dp = new int[n]; //最大序列可能不是以最后一个数结尾 int maxx = 0; for(int i=0;i<n;i++) { dp[i]=Math.max(1, dp[i]); for(int j=0;j<i;j++) { if(nums[i]>nums[j]) { dp[i]=Math.max(dp[j]+1, dp[i]); } } maxx = Math.max(maxx, dp[i]); } return maxx; } }

虽然这不是最优解，最优解是动态规划+二分：

// Dynamic programming + Dichotomy. class Solution { public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int res = 0; for(int num : nums) { int i = 0, j = res; while(i < j) { int m = (i + j) / 2; if(tails[m] < num) i = m + 1; else j = m; } tails[i] = num; if(res == j) res++; } return res; } }