方法：動態規劃

思路：

1. dp[i]含義：到i這個位置（包含i）的連續遞增子序列的長度
2. 遞推公式：if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
3. 初始化：每一個nums[i]的子序列都至少是1，就是自己。Arrays.fill(dp, 1); int maxLen = 1;
4. 遍歷方向：正序

// 動態規劃
class Solution {public int findLengthOfLCIS(int[] nums) {int n = nums.length;// dp[i]含義：到i這個位置（包含i）的連續遞增子序列的長度int[] dp = new int[n];// 初始化：每一個nums[i]的子序列都至少是1，就是自己Arrays.fill(dp, 1);int maxLen = 1;// 從1開始遍歷for (int i = 1; i < n; i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;// 刷新最大值maxLen = Math.max(maxLen, dp[i]);}}return maxLen;}
}

方法：貪心

思路：

連續遞增，就不斷len++；不連續了，就更新最大值。

如果最長串，剛好到末尾的話，出了循環還要更新一次最大值。

class Solution {public int findLengthOfLCIS(int[] nums) {int n = nums.length;// 題目說n>1。所以至少有一個nums[i]。每個nums[i]的長度都是1int len = 1;int maxLen = 1;// 從1開始遍歷（如果n==1的話，不進這個循環，答案也是對的）for (int i = 1; i < n; i++) {if (nums[i] > nums[i - 1]) {// 連續遞增len++;} else {// 不連續了。刷新最大值maxLen = Math.max(maxLen, len);// 每個nums[i]的長度都是1len = 1;}}// 如果最長串，剛好到末尾的話。maxLen還沒取到，所以出了循環還要再取一次return Math.max(maxLen, len);}
}

思路：

另一種寫法

class Solution {public int findLengthOfLCIS(int[] nums) {int n = nums.length;// 題目說n>1。所以至少有一個nums[i]。每個nums[i]的長度都是1int len = 1;int maxLen = 1;// 從1開始遍歷（如果n==1的話，不進這個循環，答案也是對的）for (int i = 1; i < n; i++) {if (nums[i] > nums[i - 1]) {// 連續遞增len++;} else {// 重新開始，每個nums[i]的長度都是1len = 1;}// 如果有更大值，刷新maxLenif (len > maxLen) {maxLen = len;}}return maxLen;}
}

方法：動態規劃

思路：

1. dp含義：dp[i]表示i之前包括i的以nums[i]結尾的最長遞增子序列的長度
2. 遞歸公式：
   • 本意就是取出最大的dp[j]+1。通俗點來講，就是接在哪個j后面，能有最大長度。
   • if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
3. 初始化：每一個nums[i]的子序列都至少是1，就是自己Arrays.fill(dp, 1);
4. 遍歷方向：正序

// 動態規劃
class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;// dp含義：dp[i]表示i之前包括i的以nums[i]結尾的最長遞增子序列的長度int[] dp = new int[n];// 題目說n>=1，所以res至少也有1int res = 1;// 初始化：每一個nums[i]的子序列都至少是1，就是自己Arrays.fill(dp, 1);// 從1開始遍歷for (int i = 1; i < n; i++) {// 從[0-i]中找，所以復雜度是O(n^2)for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {// 注意這里的max函數，本意不是為了比較dp[i]和dp[j]+1，而是為了取出本層最大的dp[i]，因為j在遍歷嘛// 本意就是取出最大的dp[j]+1。通俗點來講，就是接在哪個j后面，能有最大長度dp[i] = Math.max(dp[i], dp[j] + 1);}}// 更新resres = Math.max(res, dp[i]);}return res;}
}

方法：貪心+二分

思路來自力扣官方題解

思路：

• 考慮一個簡單的貪心，如果我們要使上升子序列盡可能的長，則我們需要讓序列上升得盡可能慢，因此我們希望每次在上升子序列最后加上的那個數盡可能的小。

• 基于上面的貪心思路，我們維護一個數組 d[i] ，表示長度為 i 的最長上升子序列的末尾元素，用 len 記錄目前最長上升子序列的長度，起始時 len 為 1，d[1]=nums[0]。

• 設當前已求出的最長上升子序列的長度為 len（初始時為 1），從前往后遍歷數組 nums，在遍歷到 nums[i] 時：

  • 如果 nums[i]>d[len] ，則直接加入到 d 數組末尾，并更新 len=len+1；
  • 否則，在 d 數組中二分查找，找到第一個比 nums[i] 小的數 d[k] ，并更新 d[k+1]=nums[i]。

// 貪心 + 二分（時間復雜度nlogn）
class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;if (n == 0) {return 0;}int len = 1;int[] d = new int[n + 1];d[len] = nums[0];for (int i = 1; i < n; i++) {if (nums[i] > d[len]) {d[++len] = nums[i];} else {// 調用二分查找函數尋找合適的位置int pos = binarySearch(d, 1, len, nums[i]);d[pos + 1] = nums[i];}}return len;}// 二分查找函數，單獨提取出來private int binarySearch(int[] d, int left, int right, int target) {int pos = 0; // 如果找不到說明所有的數都比 target 大，此時要更新 d[1]，所以這里將 pos 設為 0while (left <= right) {int mid = left - ((left - right) >> 1);if (d[mid] < target) {pos = mid;left = mid + 1;} else {right = mid - 1;}}return pos;}
}

注意，這題雖然說是“子數組”，但是實際上是按“子序列”理解。

子數組是可以重新排序的，子序列是不能改變原有的順序的（但是可以跳過一些元素）

方法：暴力

思路：

每當nums1[i] == nums2[j]的時候，記錄while(nums1[ii++] == nums2[jj++])的長度。

但是這個方法的時間復雜度很恐怖，去到O(n^3)

class Solution {public int findLength(int[] nums1, int[] nums2) {int maxLen = 0;int n1 = nums1.length;int n2 = nums2.length;for (int i = 0; i < n1; i++) {for (int j = 0; j < n2; j++) {if (nums1[i] == nums2[j]) {int ii = i;int jj = j;while (ii < n1 && jj < n2 && nums1[ii] == nums2[jj]) {ii++;jj++;}int len = ii - i;if (len > maxLen) {maxLen = len;}}}}return maxLen;}
}

方法：動態規劃（二維DP數組）

思路：

1. dp[i][j]含義：以下標i - 1為結尾的A，和以下標j - 1為結尾的B，的最長重復子數組長度
2. 遞推公式：
   • 前面的一位是相等的，那么dp[i][j]要等于dp[i - 1][j - 1] + 1，表明以下標i - 1為結尾的A，和以下標j - 1為結尾的B，最長重復子數組的長度增加了1
   • if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
3. 初始化：0
4. 遍歷順序：正序

// 動態規劃（二維DP數組）
class Solution {public int findLength(int[] nums1, int[] nums2) {int n1 = nums1.length;int n2 = nums2.length;// dp[i][j]含義：以下標i - 1為結尾的A，和以下標j - 1為結尾的B，的最長重復子數組長度int[][] dp = new int[n1 + 1][n2 + 1];int maxLen = 0;// 要從索引1開始遍歷,到索引n才結束for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {// 前面的一位是相等的，那么dp[i][j]等于前面的長度+1。（告訴后面到我這有多長重復）if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}// 刷新maxLenif (dp[i][j] > maxLen) {maxLen = dp[i][j];}}}return maxLen;}
}

方法：動態規劃（一維DP數組）

思路：

《代碼隨想錄》：

我們可以看出dp[i][j]都是由dp[i - 1][j - 1]推出。那么壓縮為一維數組，也就是dp[j]都是由dp[j - 1]推出。

也就是相當于可以把上一層dp[i - 1][j]拷貝到下一層dp[i][j]來繼續用。

此時遍歷B數組的時候，就要從后向前遍歷，這樣避免重復覆蓋。

// 動態規劃（一維DP數組）
class Solution {public int findLength(int[] nums1, int[] nums2) {int n1 = nums1.length;int n2 = nums2.length;// 因為把nums1的維度壓縮了。所以要靠nums2作為dp// 所以要遍歷nums1，nums2每層的狀態要復用int[] dp = new int[n2 + 1];int maxLen = 0;for (int i = 1; i <= n1; i++) {// 因為要用到上一層的狀態，所以要倒序遍歷for (int j = n2; j > 0; j--) {if (nums1[i - 1] == nums2[j - 1]) {dp[j] = dp[j - 1] + 1;} else {dp[j] = 0; // 注意，不相等的話，要刷回0}// 刷新maxLenif (dp[j] > maxLen) {maxLen = dp[j];}}}return maxLen;}
}