一、最长递增子序列
300. 最长递增子序列
算法原理：
💡细节：
1.注意子序列和子数组的区别：
(1)子序列：要求顺序是固定的（要求没那么高，所以子序列就多一些）
(2)子数组：要求是连着的（这个要求就必须高，所以子数组较少）
2.dp确定了以后，就不断向前推，i-1位置到i位置的最长子序列的长度，i-2到i...直到0-i位置，那么就引入一个j来记录[0,i-1]位置，j就表示上一个递增的位置，这样将dp[i]和dp[j]联系起来，注意有个前提是递增的，即nums[j]>nums[i]
3.又因为dp表示的是最长递增序列，所以需要取前面所有dp[j]位置的最大值
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
//初始化：为最小值
for(int i=0;i<n;i++) dp[i] = 1;
int ret = 1;
for(int i=1;i<n;i++) {
for(int j=0;j<i;j++) {
if(nums[j]<nums[i]) {
dp[i]=Math.max(dp[j]+1,dp[i]);//j位置为结尾的最长长度
}
}
ret = Math.max(ret,dp[i]);
}
return ret;
}
}二、摆动序列
376. 摆动序列
算法原理：
💡细节：
1.因为需要知道上一个位置是上升还是下降，所以需要两个dp表
2.根据dp表的涵义，每次求f和g的时候需要求最大值j位置结尾的最长长度
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
int[] f = new int[n];//上升
int[] g = new int[n];//下降
//初始化为最小值
for(int i=0;i<n;i++) f[i]=g[i]=1;
int ret = 1;
for(int i=1;i<n;i++) {
for(int j=0;j<i;j++) {
if(nums[j]<nums[i]) f[i]=Math.max(g[j]+1,f[i]);
else if(nums[j]>nums[i]) g[i]=Math.max(f[j]+1,g[i]);
}
ret = Math.max(ret,Math.max(f[i],g[i]));
}
return ret;
}
}三、最长递增子序列的个数
673. 最长递增子序列的个数
算法原理：
💡细节：
1.前置知识：如果通过一次遍历在数组中找出最大值出现的次数
2.dp表如果只设置一个最长序列的个数，但是不知道每个位置的最大长度，是做不了的，所以还需要设置一个dp表
3.在求最长递增子序列的基础上，需要判断上一个位置（j位置结尾）的最大长度和i位置结尾的最大长度的关系
（1）len[j]+1==len[i]：count[i]+=count[j]（最大长度+1，所以个数还是和上个位置一样）
（2）len[j]+1<len[i]：
（3）len[j]+1>len[i]：更新最大长度，并初始化count[i]为count[j]
4.返回值：跟上面前置知识一样求retcount（找retcount也就是在len[i]数组中找出最大值出现的次数）
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] len = new int[n];
int[] count = new int[n];
for(int i=0;i<n;i++) len[i]=count[i]=1;
int retlen = 1,retcount=1;
for(int i=1;i<n;i++) {
for(int j=0;j<i;j++) {
if(nums[j]<nums[i]) {
if(len[j]+1==len[i]) //计数
count[i]+=count[j];
else if(len[j]+1>len[i]) {//重新计数
len[i]=len[j]+1;
count[i]=count[j];
}
}
}
if(retlen==len[i]) retcount+=count[i];
else if(retlen<len[i]) {
retlen = len[i];
retcount = count[i];
}
}
return retcount;
}
}四、最长数对链
646. 最长数对链
算法原理：
💡细节：
1.预处理：按照第一个元素排序（因为当计算dp[i]的时候，会发现倒数第二个位置可能是在i的左边，也可能在i的右边，所以要先进行排序）
2.其他部分跟 最长递增子序列 这题一样，只需将比较的值改为pairs[j][1]和pairs[i][0]即可
class Solution {
public int findLongestChain(int[][] pairs) {
//预处理
Arrays.sort(pairs,(a,b)->a[0]-b[0]);
int n = pairs.length;
int[] dp = new int[n];
for(int i=0;i<n;i++) dp[i] = 1;
int ret = 1;
for(int i=0;i<n;i++) {
for(int j=0;j<i;j++) {
if(pairs[j][1]<pairs[i][0]) {
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
ret = Math.max(ret,dp[i]);
}
return ret;
}
}
