题目链接:
链接
题目描述:
思路:
思路一:动态规划
类似于“单词拆分”,需要遍历之前的元素 对应的最大长度,然后找到最大的
设第 i i i个元素对应的最长递增序列长度是 d p ( i ) dp(i) dp(i),每一个 d p ( i ) dp(i) dp(i)最初都是1
则:当 n u m s [ i ] > n u m s [ j ] nums[i] > nums[j] nums[i]>nums[j] 时,有
d p ( i ) = m a x { d p ( i ) , d p ( j ) + 1 } dp(i) = max\{ dp(i) ,dp(j) + 1 \} dp(i)=max{dp(i),dp(j)+1}
返回dp中的最大值就行
思路二
贪心 + 二分查找
要找最长的递增序列,就期望递增的幅度最小,相同长度下,递增的幅度越小,后面可以满足递增的元素就越多(不一定),按照这种思路写代码会存在一个问题:我们并不知道后面是否会有更多的满足递增的元素,如:0 2 6 7 4,最长的是0 2 6 7,但是按照上面的思路我们会选择0 2 4,
所以,我们也需要记录下已经遍历到的最长的递增序列及长度,我们可以使用一个数组d记录“已经遍历到的最长的递增序列”,如 0 2 6 7 len = 4,
如果有更长的递增序列,d里面的元素就应该被覆盖掉
怎么覆盖呢?当我们遇到更小的元素后,就可以把更小的元素放进d里面合适的位置使d继续满足递增,如0 2 4 7
- 如果后面有 相对于4 递增的数据(假设原数组是:0 2 6 7 4 5 6):则d变成 0 2 4 5 6,len=5
- 如果后面是 相对于7 递增的数据(假设原数组是:0 2 6 7 4 8):则d变成 0 2 4 7 8
(这里d从索引1开始存放元素)
总结:
- 如果 d [ j ] < n u m [ i ] < d [ l e n ] d[j]<num[i] < d[len] d[j]<num[i]<d[len],就把 n u m [ i ] num[i] num[i]放入d数组中间
- 如果 n u m [ i ] > d [ l e n ] num[i] > d[len] num[i]>d[len],就把 n u m [ i ] num[i] num[i]放入d数组末尾,同时len++
这里 “把 n u m [ i ] num[i] num[i]放入d数组中间”,可以用二分法
注意:最后得到的d数组不一定是最长递增序列,实际上d只能记录某个最长序列的最后一个元素d[len]
实现代码:
class Solution {public int lengthOfLIS(int[] nums) {if(nums.length == 0) return 0;int[] dp = new int[nums.length];//这里直接用 当前元素的位置 存放 最大长度就行dp[0] = 1;int ans = 1;for(int i = 1; i < nums.length; i++){dp[i] = 1;for(int j = 0; j < i; j++){if(nums[i]>nums[j]){dp[i] = Math.max(dp[i],dp[j]+1);}}ans = Math.max(ans,dp[i]);}return ans;}
}
class Solution {public int lengthOfLIS(int[] nums) {int len = 1, n = nums.length;if(n ==0) {return 0;}int[] d = new int[n+1];d[len] = nums[0];//的d[1] = nums[0]for(int i = 1; i < n; i++){if(nums[i]>d[len]){d[++len] = nums[i];}else{int left = 1, right = len, pos = 0;//pos表示d里面小于nums[i]的数的索引while(left <= right){int mid = (right -left) / 2 + left;if(d[mid] < nums[i]){pos = mid;left = mid + 1;}else{right = mid - 1;}}d[pos + 1] = nums[i];}}return len;}
}