中国肩章大全图解_外贸进出口代理公司_网页制作接单平台_培训学校机构有哪些

题目链接：

链接

题目描述：

思路：

思路一：动态规划

类似于“单词拆分”，需要遍历之前的元素 对应的最大长度，然后找到最大的
设第$i$个元素对应的最长递增序列长度是$dp(i)$，每一个$dp(i)$最初都是1

则：当 $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]<num[i]<d[len]$，就把$num[i]$放入d数组中间
• 如果$num[i]>d[len]$，就把$num[i]$放入d数组末尾，同时len++

这里 “把$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;}
}