算法刷题记录 Day46

算法刷题记录 Day46

Date: 2024.04.13

lc 53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // dp[i]表示以nums[i]结尾的连续子数组的最大和；
        // dp[i] = max(nums[i], dp[i-1]+nums[i]);若之前的最大和小于0，则舍弃；
        int n = nums.size();
        int before_num = nums[0];

        int max_sum = nums[0];

        for(int i=1; i<n; i++){
            before_num = max(nums[i], before_num + nums[i]);
            max_sum = max(max_sum, before_num);
        }
        

        // for(int i=0; i<n; i++){
        //     cout<<"i:"<<i<<", dp[i]:"<<dp[i]<<endl;
        // }
        return max_sum;
    }
};

lc 1035. 不相交的线

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        // 实际上就是求两个数组中，最多的相同个数, 即最长公共子序列
        // dp[i][j]表示数组nums1中[0,i]和nums2中[0,j]的最大连线数；
        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> dp(m, vector<int>(n, 0));

        // dp初始化，第一行和第一列
        for(int i=0; i<m; i++){
            if(nums1[i] == nums2[0]){
                while(i<m){
                    dp[i][0] = 1;
                    i++;
                }
                break;
            }
        }
        for(int j=0; j<n; j++){
            if(nums2[j] == nums1[0]){
                while(j<n){
                    dp[0][j] = 1;
                    j++;
                }
                break;
            }
        }

        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(nums1[i] == nums2[j])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        return dp[m-1][n-1];
    }
};

lc 1143. 最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // dp[i][j]表示text1[0,i]，text2[0,j]时的最长公共子序列长度。
        // 易得性质1:dp[i][j] >= max(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]);
        // dp[i][j]可以由任意i,j比当前小的里推出。由于性质1，因此可以由dp[i-1][j-1]推出。
        int len1 = text1.size();
        int len2 = text2.size();
        vector<vector<int>> dp(len1, vector<int>(len2, 0));
        // dp初始化：由i-1,j-1推出，因此需要初始化第一行和第一列；
        
        for(int i=0; i<len1; i++){
            if(text1[i] == text2[0] || (i >= 1 && dp[i-1][0] == 1))
                dp[i][0] = 1;
        }
        for(int j=0; j<len2; j++){
            if(text1[0] == text2[j] || (j >= 1 && dp[0][j-1] == 1))
                dp[0][j] = 1;
        }

        for(int i=1; i<len1; i++){
            for(int j=1; j<len2; j++){
                if(text1[i] == text2[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1]));
                }
            }
        }

        // for(int i=0; i<len1; i++){
        //     for(int j=0; j<len2; j++){
        //         cout<<"i, j:"<<i<<", "<<j<<" dp[i][j]:"<<dp[i][j]<<endl;
        //     }
        // }

        return dp[len1-1][len2-1];
        
    }
};