300.最长递增子序列
思路：
子序列问题是动态规划解决的经典问题，当前下标i的递增子序列长度，其实和i之前的下表j的子序列长度有关系，那又是什么样的关系呢。
接下来，我们依然用动规五部曲来详细分析一波：
- dp[i]的定义
本题中，正确定义dp数组的含义十分重要。
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。 - 状态转移方程
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。
- dp[i]的初始化
每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1. - 确定遍历顺序
dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。
j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。 - 举例推导dp数组
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp=new int[nums.length];//dp数组表示以dp[i]为结尾的最长递增子序列
for(int i=0;i<nums.length;i++){//初始化，因为至少为1
dp[i]=1;
}
int max=1;
for(int i=1;i<nums.length;i++){//遍历顺序都是从小到大
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=Math.max(dp[i],dp[j]+1);//递推公式
if(dp[i]>max){
max=dp[i];
}
}
}
}
return max;//注意：并不一定是dp[len-1]才是最大的
}
}
时间复杂度：
O
（
n
2
）
O（n^2）
O（n2）
空间复杂度：
O
（
n
）
O（n）
O（n）
674. 最长连续递增序列
思路： 这道题用贪心也很容易实现，使用一个变量temp记录包含当前位置的连续子序列长度，max记录最大的长度。
贪心实现
class Solution {
public int findLengthOfLCIS(int[] nums) {
int max=1;
int temp=1;
for(int i=1;i<nums.length;i++){
if(nums[i]>nums[i-1]){
temp++;
}else{
temp=1;
}
if(temp>max) max=temp;
}
return max;
}
}
时间复杂度：
O
（
n
）
O（n）
O（n）
空间复杂度：
O
（
1
）
O（1）
O（1）
动态规划实现
/**
* 1.dp[i] 代表当前下标最大连续值
* 2.递推公式 if（nums[i+1]>nums[i]） dp[i+1] = dp[i]+1
* 3.初始化 都为1
* 4.遍历方向，从其那往后
* 5.结果推导 。。。。
* @param nums
* @return
*/
public static int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
for (int i = 0; i < dp.length; i++) {
dp[i] = 1;
}
int res = 1;
//可以注意到，這邊的 i 是從 0 開始，所以會出現和卡哥的C++ code有差異的地方，在一些地方會看到有 i + 1 的偏移。
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] > nums[i]) {
dp[i + 1] = dp[i] + 1;
}
res = res > dp[i + 1] ? res : dp[i + 1];
}
return res;
}
时间复杂度：
O
（
n
）
O（n）
O（n）
空间复杂度：
O
（
n
）
O（n）
O（n）
718. 最长重复子数组
关键在于dp数组的含义是以i，j为结尾的子数组！根据nums[i]和nums[j]的关系判断与上一个状态的递推关系。dp数组初始为0；
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[][] dp=new int[nums1.length+1][nums1.length+1];//定义成len+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;
}
max=Math.max(dp[i][j],max);
}
}
return max;
}
}
时间复杂度：
O
（
n
∗
m
）
O（n*m）
O（n∗m）
空间复杂度：
O
（
n
∗
m
）
O（n*m）
O（n∗m）
