目录
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
示例 2：
示例 3：
提示：
? ? ? ? ? ?能否用贪心？没想到办法
? ? ? ? ? ? 用动态规划没想到怎么解决
????????
? ? ? ? 用动态规划
? ? ? ? 确定dp数组和每个下标的含义
? ? ? ? dp[i]记录末尾为i的最长的递增子序列的长度
? ? ? ? 确定递推公式
? ? ? ? 用j 从0遍历到i 若dp[j]<dp[i] 则dp[i] = max(dp[i],dp[j]+1);
? ? ? ? dp数组初始化
? ? ? ? 都为1 ，因为最小为1
? ? ? ? 确定遍历顺序
? ? ? ? 从前往后从后往前都可以
? ? ? ? 从前往后比较习惯
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 遍历dp数组打印最大的那个值
? ? ? ? 取得的dp值为max(dp[i],dp[j]+1)，因为dp[i]是不断地在变化的，所以要不断地与dp[i]作比较调整
? ? ? ? 打印的方式，打印的是dp数组中最大的那个值
????????
class Solution {
public int lengthOfLIS(int[] nums) {
//我的做法，贪心
//卡哥做法
//确定dp数组和每个下标的含义
//dp[j] 到达j这个位置的最长递增子序列的长度
//确定递推函数 不断地和i进行比较，若当前的dp[j]比dp[i]小，则赋值dp[j]+1给dp[i]
// dp[i可能会随着j的变化，变化多次，选最大的一个
//若dp[j]<dp[i] dp[i]=Math.max(dp[j]+1,dp[i])
//dp数组初始化
//全都默认为1，代表自身
//确定遍历顺序
//从前往后从后往前都可以
//举例推导dp数组
//打印dp数组
//选择整个dp中的最大值
int[] dp = new int[nums.length];
for(int i=0;i<dp.length;i++){
dp[i] = 1;
}
for(int i=0;i<nums.length;i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
}
int maxNum=0;
for(int i=0;i<dp.length;i++){
maxNum = dp[i]>maxNum?dp[i]:maxNum;
}
return maxNum;
}
}? ? ? ?
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
示例 2：
提示：
? ? ? ? ? ? 都写出来了
? ? ? ? ? ?能否用贪心？可以，而且更方便
? ? ? ? ? ? 用动态规划，若nums[i-1]<nums[i] 则dp[i] = dp[i-1]+1
? ? ? ? ? ?dp记录的最长连续递增序列
????????
? ? ? ? 用动态规划
? ? ? ? 确定dp数组和每个下标的含义
? ? ? ? dp[i]记录末尾为i的最长的连续递增子序列的长度
? ? ? ? 确定递推公式
? ? ? ? 遍历nums ，若nums[i-1]<nums[i] 则dp[i] = dp[i-1]+1
? ? ? ? dp数组初始化
? ? ? ? 都为1 ，因为最小为1
? ? ? ? 确定遍历顺序
? ? ? ? 从前往后
? ? ? ? 从前往后比较习惯
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 遍历dp数组打印最大的那个值
? ? ? ? 贪心的if else 和result 的写法，可以学一下
? ? ? ? ????????if(){
? ? ? ? ? ? ? ? count++
????????????????}else{
? ? ? ? ? ? ? ? count=1
????????????????}
? ? ? ? ? ? ? ? if(count>result){
? ? ? ? ? ? ? ? result = count;
????????????????}
????????
class Solution {
public int findLengthOfLCIS(int[] nums) {
//贪心也可以
//从递增开始记录
if(nums.length==1){
return 1;
}
int count =1;
int result = 1;
//这种result 和count赋值的方式可以学一下，else count=1 ，和if(count>result) count = result;
for(int i=1;i<nums.length;i++){
if(nums[i-1]<nums[i]){
count++;
}else{
count=1;
}
if(count>result){
result=count;
}
}
return result;
//确定dp数组，和每个下标的定义
//dp[i] 到下标i最大递增长度
//确定递推公式
//if(dp[i]<dp[i+1])
//dp[i]=dp[i-1]+1
//确定遍历顺序
//从前往后
//dp数组初始化
//都默认为1
//举例推导dp数组
/*int[] dp = new int[nums.length];
for(int i=0;i<dp.length;i++){
dp[i]=1;
}
//maxNum要初始化为1，因为最小的是1
int maxNum = 1;
for(int i=1;i<nums.length;i++){
if(nums[i-1]<nums[i]){
dp[i]=dp[i-1]+1;
}
maxNum = maxNum>dp[i]?maxNum:dp[i];
}
return maxNum;*/
}
}给两个整数数组?A?和?B?，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
提示：
? ? ? ? 卡哥提示使用二维数组
? ? ? ? 怎么用二维数组来做呢？
? ? ? ? 这道题求的是两个数组的公共的最长子数组的长度，那么dp[i][j]可以用来视作，nums1到达i，nums[2]到达j的最长公共序列的长度
? ? ? ? 确定递推公式
? ? ? ? ?dp[i][j] = dp[i-1][j-1]+1
? ? ? ? 为什么是i-1 和j-1 因为它们两个都需要一起往前走，和往后走来判断是否相同
? ? ? ? 确定遍历顺序
? ? ? ? 先nums1? 再nums2?
? ? ? ? dp数组初始化
? ? ? ? dp[0][I]:nums1[0] 与 nums2[i] 相等则dp[0][i]为1其余 为0
? ? ? ? dp[i][0]:nums1[i] 与nums2[0] 相等则dp[i][0]为1 其余为0
? ? ? ? 打印dp数组
? ? ? ? 找到最大值并返回
????????
? ? ? ? 卡哥思路更方便，且不需要初始化
? ? ? ? 用动态规划
? ? ? ? 确定dp数组和每个下标的含义
????????那么dp[i][j]可以用来视作，nums1到达i-1，nums2到达j-1的最长公共序列的长度
? ? ? ? 确定递推公式
? ? ? ? 若nums[i-1]=nums[j-1] 则 dp[i][j] = dp[i-1][j-1]+1
? ? ? ? dp数组初始化
? ? ? ? 都为0 因为dp[0][I]和dp[i][0]代表第一行第一列 ,在dp中是代表nums1[-1] 和nums2[-1]是没有意义的?
? ? ? ? 确定遍历顺序
? ? ? ?nums1 or nums2 都随便遍历
???????? 从前往后
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 遍历dp数组打印最大的那个值
? ? ? ?注意卡哥这种实现方式方便
? ? ? ? 我的实现方式中要在初始化重置max的值
? ? ? ? 卡哥的dp数组的长度为nums.length+1
class Solution {
public int findLength(int[] nums1, int[] nums2) {
/*//卡哥提示用二维数组，自己做出来了
//确定dp数组和每个下标的含义
//二维数组 dp[i][j] 到达i,j位置两个数组的公共的最长的子数组的长度
//确定递推公式
//若nums1[i]==nums2[j] dp[i][j]=dp[i-1][j-1]+1;
//dp数组初始化
//第一行和第一列
//若和nums1[0]相等则为1
//若和nums2[0]相等则为1
//确定遍历顺序
// 先nums1 再nums2
//举例推导dp数组
int[][] dp = new int[nums1.length][nums2.length];
int max = 0;
for(int i=0;i<nums1.length;i++){
if(nums1[i]==nums2[0]){
dp[i][0]=1;
max=1;
}
}
for(int i=0;i<nums2.length;i++){
if(nums2[i]==nums1[0]){
dp[0][i]=1;
max=1;
}
}
for(int i=1;i<nums1.length;i++){
for(int j=1;j<nums2.length;j++){
if(nums1[i]==nums2[j]){
dp[i][j]=dp[i-1][j-1]+1;
}
if(dp[i][j]>max){
max = dp[i][j];
}
}
}
return max;*/
//卡哥做法:不需要初始化dp[0][i] 和dp[i][0]了
//确定dp数组和每个下标的含义
//dp的大小 length+1
//二维数组 dp[i][j] 到达i-1,j-1位置两个数组的公共的最长的子数组的长度
//确定递推公式
//若nums1[i]==nums2[j] dp[i][j]=dp[i-1][j-1]+1;
//dp数组初始化
//第一行和第一列
//全为0就可以了
//确定遍历顺序
//都可以
// 先nums1 再nums2
//举例推导dp数组
int[][] dp = new int[nums1.length+1][nums2.length+1];
int max = 0;
for(int i=1;i<=nums1.length;i++){
for(int j=1;j<=nums2.length;j++){
if(nums1[i-1]==nums2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
if(dp[i][j]>max){
max = dp[i][j];
}
}
}
return max;
}
}