Day 52 動(dòng)態(tài)規(guī)劃

300. 最長遞增子序列

我自己想出來的方法，時(shí)間復(fù)雜度應(yīng)該是O(n2)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 1) return 1;
        vector<int> dp(nums.size(), 1);
        int maxCnt = INT_MIN;

        for (int i = 1; i < nums.size(); i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (nums[j] < nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                    // break;
                }
                if (maxCnt < dp[i])
                {
                    maxCnt = dp[i];
                }
            }
        }

        return maxCnt;
    }
};

674. 最長連續(xù)遞增序列

滑動(dòng)窗口

連續(xù)的話，可以考慮用滑動(dòng)窗口文章來源地址http://www.zghlxwxcb.cn/news/detail-621690.html

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int left = 0, right = 1, maxLen = 1;

        while (right < nums.size())
        {
            if (nums[right] <= nums[right - 1])
            {
                int len = right - left;
                if (len > maxLen)
                {
                    maxLen = len;
                }
                left = right;
            }
            right++;
        }

        int len = right - left;
        if (len > maxLen)
        {
            maxLen = len;
        }
        left = right;

        return maxLen;
    }
};

動(dòng)態(tài)規(guī)劃

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int maxCnt = 1;
        vector<int> dp(nums.size(), 1);

        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] > nums[i - 1])
            {
                dp[i] = max(dp[i], dp[i - 1] + 1);
            }
            if (maxCnt < dp[i])
            {
                maxCnt = dp[i];
            }
        }

        return maxCnt;
    }
};

貪心算法

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int maxCnt = 1, curCnt = 1;

        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] > nums[i - 1])
            {
                curCnt++;
                if (maxCnt < curCnt)
                {
                    maxCnt = curCnt;
                }
            }
            else
            {
                curCnt = 1;
            }
        }

        return maxCnt;
    }
};

718. 最長重復(fù)子數(shù)組

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size() + 1, n = nums2.size() + 1, maxCnt = 0;
        vector<vector<int>> dp(m, vector<int>(n, 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] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
                if (dp[i][j] > maxCnt)
                {
                    maxCnt = dp[i][j];
                }
            }
        }

        return maxCnt;
    }
};

到了這里，關(guān)于算法刷題Day 52 最長遞增子序列+最長連續(xù)遞增子序列+最長重復(fù)子數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！