Day 52 动态规划
300. 最长递增子序列
我自己想出来的方法,时间复杂度应该是O(n2)
文章来源:https://www.toymoban.com/news/detail-621690.html
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. 最长连续递增序列
滑动窗口
连续的话,可以考虑用滑动窗口文章来源地址https://www.toymoban.com/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;
}
};
动态规划
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. 最长重复子数组
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;
}
};
到了这里,关于算法刷题Day 52 最长递增子序列+最长连续递增子序列+最长重复子数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!