300.最長遞增子序列

**題目：**給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴格遞增子序列的長度。子序列 是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

題目鏈接：300.最長遞增子序列
解題思路：
dp數(shù)組的含義：以nums[i]結(jié)尾的最長遞增子數(shù)組
所以當該序列以nums[i] 結(jié)尾時，遍歷nums的0至i-1
當該數(shù)字nums[j]小于nums[i] 證明可以以nums[i] 結(jié)尾 此時dp[i]=dp[j]+1
因為有多個滿足條件的nums[j],取最大值
遞推公式為：
dp[i]=Math.max(dp[i],dp[j]+1);
最終的最大值不一定以nums[nums.length-1]結(jié)尾，所以需要維護一個int類型的max
代碼如下：

class Solution {public int lengthOfLIS(int[] nums) {if(nums.length==1){return 1;}//dp[n]含義 以nums[n-1]為結(jié)尾的嚴格遞增子序列長度int n=nums.length;int[] dp=new int[n];dp[0]=1;Arrays.fill(dp, 1);int res = 0;for(int i=1;i<n;i++){//遞推公式//遍歷i前面的數(shù)確定是否加入數(shù)組for(int j=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=Math.max(dp[i],dp[j]+1);}}res = Math.max(res, dp[i]);}return res;            }
}

674. 最長連續(xù)遞增序列

代碼如下：

  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 開始，所以會出現(xiàn)和卡哥的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;}

718. 最長重復子數(shù)組

題目：給兩個整數(shù)數(shù)組 nums1 和 nums2 ，返回 兩個數(shù)組中 公共的 、長度最長的子數(shù)組的長度 。
示例 1：
輸入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
輸出：3
解釋：長度最長的公共子數(shù)組是 [3,2,1] 。
示例 2：
輸入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
輸出：5
題目鏈接： 718. 最長重復子數(shù)組
解題思路：
1.dp數(shù)組的含義 數(shù)組【0-nums[i-1]】與【0-nums[j-1]】的最長公共后綴
2.遞推公式 即當A[i - 1] 和B[j - 1]相等的時候，dp[i][j] = dp[i - 1][j - 1] + 1;
3.為什么要記錄最大值 因為要求的是最長數(shù)組的公共子序列，最長公共后綴不一定是最長公共數(shù)組產(chǎn)生的
代碼如下：

class Solution {public int findLength(int[] nums1, int[] nums2) {int result = 0;int[][] dp = new int[nums1.length + 1][nums2.length + 1];for (int i = 1; i < nums1.length + 1; i++) {for (int j = 1; j < nums2.length + 1; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;result = Math.max(result, dp[i][j]);}}}return result;}
}