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 i0;in;i) { dp[i]Math.max(1, dp[i]); for(int j0;ji;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; } }