題1：
指路：300. 最長遞增子序列 - 力扣（LeetCode）
思路與代碼：
求最長遞增子序列，那么就定義一個數組dp[i]，含義為最長遞增子序列。這里有一個小問題，這里的序列的范圍為何。如果把遍歷范圍定為全數組那和暴力無異，顯然也不符合O(nlogn)的要求。那么在這里我們定義遍歷范圍的時候就要把dp[i]定義為以nums[i]結尾的最長遞增子序列的長度。隨后我們定義一個j在i的范圍內遍歷，當nums[i]>nums[j]時，在這里就得到了一個dp[i]=dp[j]+1，而我們要求的是最大遞增子序列，那么要在原有的dp[i]和得到的dp[i]中取較大值，也就是dp[i]=max(dp[i], dp[j] + 1)。最后我們看需要輸出的是什么，在樣例中我們可以看到絕對不再是dp[nums.size()-1]，我們需要的是整個數組的最長遞增子序列，那么就需要遍歷整個數組的dp值，取出最大的即可。代碼如下：
class Solution {
public:int lengthOfLIS(vector<int>& nums) {// dp數組的含義為最長遞增子序列長度if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);dp[0] = 1;int result = 0;// 遞推for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = max(dp[j] + 1, dp[i]);}if (dp[i] > result) result = dp[i];}}return result ;}
};題2：
指路：674. 最長連續遞增序列 - 力扣（LeetCode）
思路與代碼：
1.動態規劃
區別于上題者為“連續”。連續就很方便了，比較清楚相鄰的兩個就好了，也就是nums[i]與nums[i-1]是否相等。注意這里的子序列，即使最短也是1，因此，result初始為1。代碼如下：
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;vector<int> dp(nums.size(), 1);int result = 1;dp[0] = 1;for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};2.貪心
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;int count = 1;for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) {count++;}else {count = 1;}if (count > result) result = count;}return result;}
};題3：
指路：718. 最長重復子數組 - 力扣（LeetCode）
思路與代碼：
兩個數組，那么不妨定義一個二維數組記錄兩個數組的比較情況，dp[i][j]的含義為以下標i-1為尾和j-1為尾的最長重復子數組的長度為dp[i][j]。將尾劃定為i-1和j-1而非i和j的原因是，在初始化數組時如果尾為i,j，那么我們需要對數組進行兩行的初始化：
for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1;for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;?而如果將尾劃為i-1和j-1時，初始化直接定義為0即可。我們讀題可以知道dp[i][j]的狀態得于前面的狀態，即dp[i][j]=dp[i-1][j-1] + 1，因為在比較兩個數組中元素后，兩個數組中的元素都需要后退一個從而達到比較全者的要求。在這里遍歷順序無謂先后，選擇最普通的一種，外層數組1，內層數組2。注意，因為前面將界限劃定為i-1，所以這里要想遍歷完數組1，那么i的取值范圍就是小于等于nums1.size()，同理，j的遍歷范圍也一樣。代碼如下：
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}if (dp[i][j] > result) result = dp[i][j];}}return result;}
};
