LeetCode 300最长递增子序列 674最长连续递增序列 718最长重复子数组 | 代码随想录25期训练营day52

2023-12-15 14:58:04

动态规划算法10

LeetCode 300 最长递增子序列 2023.12.15

int lengthOfLIS(vector<int>& nums) {
    //创建变量result存储最终答案,设默认值为1
    int result = 1;
    //1确定dp数组,dp[i]表示以nums[i]为结尾的子数组的最长长度
    vector<int> dp(nums.size(), 1);
    //3初始化,所有元素默认的长度都为1,在创建时均已初始化
    //2确定递推公式,4确定遍历顺序
    //递推公式dp[i]表示以nums[i]为结尾的最长长度=max(以比nums[i]小的值结尾的最长长度+1(nums[i]),dp[i])
    //先正序遍历nums数组,然后可以正序或倒序遍历(0, i)更新dp[i]
    for (int i = 1; i < nums.size(); i++)
    {

        for (int j = 0; j < i; j++)
        {
            if(nums[j] < nums[i])
                dp[i] = max(dp[j] + 1, dp[i]);
        }
        //更新result值,为当前数组的递增序列最长长度
        if(result < dp[i])
            result = dp[i];
    }
    return result;
}

LeetCode 674 最长连续递增序列 2023.12.15

int findLengthOfLCIS(vector<int>& nums) {
    //创建变量result存储最终答案,设默认值为1
    int result = 1;
    //1确定dp数组,dp[i]表示以nums[i]为结尾的连续递增子数组的最长长度
    vector<int> dp(nums.size(), 1);
    //3初始化,所有元素默认的长度都为1,在创建时均已初始化
    //2确定递推公式,4确定遍历顺序
    //递推公式dp[i]表示:如果nums[i-1]<nums[i],
    //那么以nums[i]为结尾的连续递增子数组最长长度=dp[i-1]+1
    for (int i = 1; i < nums.size(); i++)
    {
        if(nums[i] > nums[i-1])
            dp[i] = dp[i-1] + 1;
        //更新result值,为当前数组的递增序列最长长度
        if(result < dp[i])
            result = dp[i];
    }
    return result;
}

LeetCode 718 最长重复子数组 2023.12.15

int findLength(vector<int>& nums1, vector<int>& nums2) {
    //创建变量result存储最终答案,设默认值为1
    int result = 0;
    //1确定dp二维数组,dp[i][j]表示以nums1[i-1]、nums2[j-1]结尾的相同子数组的最大长度
    vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));
    //3初始化,第一行和第一列必须初始化,意义上为0
    //2确定递推公式,4确定遍历顺序
    //如果nums1[i-1]、nums2[j-1]相同,那么dp[i][j]+1
    //顺序遍历
    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(result < dp[i][j])
                result = dp[i][j];
        }
    }
    return result;
}

文章来源:https://blog.csdn.net/weixin_66706867/article/details/135014975
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。