【c++刷题笔记-动态规划】day43： 300.最长递增子序列 、 674. 最长连续递增序列、 718. 最长重复子数组

300. 最长递增子序列 - 力扣（LeetCode）

思路：让以当前的下标为i的数与i前面的所有数比较获取最大值

重点： dp[i]=max(dp[i],dp[j]+1);

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        if(n==1){
            return 1;
        }
        int ans=0;
        vector<int>dp(n,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    //当前i与i前面的所有数字也就是每一个j比较获取最大值
                    dp[i]=max(dp[i],dp[j]+1);
                }
                if(dp[i]>ans){
                    ans=dp[i];
                }
            }
        }
        return ans;
    }
};

674. 最长连续递增序列 - 力扣（LeetCode）

思路：找出以i下标的数为结尾的个数，取最大值

重点：dp[i]=dp[i-1]+1;

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n=nums.size();
        int ans=1;
        vector<int>dp(n,1);
        for(int i=1;i<n;i++){
            if(nums[i]>nums[i-1]){
                dp[i]=dp[i-1]+1;//以i下标的数为结尾的个数
            }
            if(dp[i]>ans){
                ans=dp[i];
            }
        }
        return ans;
    }
};

 718. 最长重复子数组 - 力扣（LeetCode）

思路：求以i-1和j-1为结尾的最大重复子数组，取最大值

重点：dp[i][j]=dp[i-1][j-1]+1; 因为相同的子数组所以要同时移动下标

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

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

总结

子序列和子数组问题，使用以i-1为结尾统计每一个最大值

原文地址：https://blog.csdn.net/qq_48662659/article/details/140519685

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！