这题动态规划比较容易想到，dp[i]就是表示以nums[i]为结尾的数组最长递增子序列的长度，递推公式就是找到比当前值小的数（保证连续）的dp值+1，时间复杂度是O(n^2)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // dp[i]表示以nums[i]的数组最长递增子序列的长度
        vector<int> dp(n, 1); 
        for(int i=1; i<n; ++i)
            for(int j=i-1; j>=0; --j)
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
        return *max_element(dp.begin(), dp.end());
    }
};

这题在时间复杂度上还有优化的点，可以看到在二重循环中，即使我们已经找到比当前值小的数a后仍需遍历完，因为之后可能还会有比当前值小的数b，且可能是最长递增子序列，因为以a结尾的最长递增子数组长度可能比以b结尾的短。而假设我们知道之前的遍历情况，记录每个递增子数组的结尾元素，贪心的想，我们只需要记录同一长度的递增子数组最小的结尾元素即可。
所以，我们可以修改dp数组的含义，dp[i]表示长度为i递增子数组的最小结尾元素。并且，在此定义下，dp数组一定是单调递增的，可以由反证法得出。
知道这个之后，我们在第二重循环中就不需要遍历所有，采用二分查找到比当前元素小的值即可。可以将时间复杂度降到O(nlogn)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // 表示长度为i的递增子序列的最小尾数
        vector<int> dp(n + 1, INT_MIN); 
        int Len = 0;  // 当前最长递增子序列长度
        for(int i=0; i<n; ++i){
            if(nums[i] > dp[Len]){
                dp[++Len] = nums[i];
            }else if(nums[i] < dp[Len]){
                // 开始二分查找
                int left = 1, right = Len;
                while(left <= right){
                    int mid = (right - left) / 2 + left;
                    if(dp[mid] < nums[i])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
                dp[left] = nums[i];
            }
        }
        return Len;
    }
};

这题要求子序列连续，就很简单了，一旦遇到破坏连续子序列的单调性的值，则重新开始，秒杀，代码如下：

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for(int i=1; i<n; ++i)
            if(nums[i] > nums[i-1])
                dp[i] = dp[i-1] + 1;
        return *max_element(dp.begin(), dp.end());
    }
};

优化空间复杂度

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 1, Len = 1;
        for(int i=1; i<nums.size(); ++i){
            Len = (nums[i] > nums[i-1] ? Len + 1 : 1);
            ans = max(ans, Len);
        }
        return ans;
    }
};

需要在两个数组内寻找到最长重复子数组，这个子数组是连续的。我们采用动态规划的思想来解决这个问题，dp数组是二维的，dp[i][j]表示以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度。递推关系是 如果A[i]==B[j]，则$dp[i+1][j+1]=d[i][j]+1$，这点毋庸置疑；如果A[i]！=B[j]时，由于要求子数组是连续的，所以此时$dp[i+1][j+1]=0$。由于我们需要找到最长重复子数组，并非一定是以某某为结尾的，所以需要取每个的dp值进行比较，取最大值。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        int ans = 0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(nums1[i]==nums2[j])
                    dp[i+1][j+1] = dp[i][j] + 1;
                ans = max(ans, dp[i+1][j+1]);
            }
        }
        return ans;
    }
};

由递推公式可以发现，当前dp值只与其左上角的dp值有关，则二维数组空间可以进一步优化成一维数组，代码如下，注意j的递归顺序发生了变化，变成了逆向遍历：

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<int>dp(n + 1);
        int ans = 0;
        for(int i=0; i<m; ++i){
            for(int j=n-1; j>=0; --j){
                dp[j+1] = (nums1[i]==nums2[j] ? dp[j] + 1 : 0);
                ans = max(ans, dp[j+1]);
            }
        }
        return ans;
    }
};