leetcode_day45

今日内容：

• 300. 最长递增子序列 medium
• 674. 最长连续递增子序列 easy
• 718. 最长重复子数组 medium

300. 最长递增子序列

题目：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路：

\(dp[i]\)表示以\(nums[i]\)结尾的最长递增子序列长度，强制以\(nums[i]\)结尾为的是方便状态转移，状态转移方程为：

\[ dp[i]\ = \begin{cases} 1, & \text{$i = 1$} \\ max(dp[j] + 1, dp[i]), & \text{$i > 1,\ j=0,1,2,……,i-1$} \end{cases} \]

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() <= 1) return 1;
        vector<int> dp(nums.size(), 1);
        int ans = 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]);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

674. 最长连续递增子序列

题目：

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

思路：

这题感觉就像贪心一样，一直换起点就好，dp换起点就是重新把长度改成1

dp[i]表示以i结尾的最长连续递增序列长度，状态转换方程为：

\[ dp[i]\ = \begin{cases} 1, & \text{$nums[i] ≤ nums[i - 1]$}\\ dp[i - 1] + 1, & \text{$nums[i]≥nums[i-1]$} \end{cases} \]

代码

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

            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

718. 最长重复子数组

题目：

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

思路：

由于两个数组的公共子数组起点可能不一样，所以得用\(i\)和\(j\)分别表示从\(nums1\)的\(i\)和\(nums2\)的\(j\)开始。

状态转移方程为：(前提条件都为nums1[i] == nums2[j])

\[ dp[i][j]\ = \begin{cases} 1, & \text{$i=0\ or\ j=0$} \\ dp[i-1][j-1]+1, & \text{else} \end{cases} \]

代码

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