本文主要是介绍leetcode 674 最长连续递增序列 C/C++ 动态规划,动态规划空间优化,双指针 三种解法,初识动态规划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#if 0
class Solution { //动态规划
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size());
int max = 0;
for(int i = 0;i< nums.size()-1; i++){
if(nums.at(i+1)> nums.at(i)) {
dp.at(i+1) = dp.at(i) + 1;
}
if(dp.at(i+1) > max) max = dp.at(i + 1);
}
return max+1;
}
};
#endif
#if 0
class Solution { //动态规划 空间优化
public:
int findLengthOfLCIS(vector<int>& nums) {
int LengthOfLCIS = 1; //保存上一次计算的连续递增的子序列的长度
int max = 1; // 保存最长的子序列的长度
for(int i = 0;i< nums.size()-1; i++){
if(nums.at(i+1)> nums.at(i)) { //如果连续递增,长度增加
LengthOfLCIS++;
}else{ //不递增了,恢复原样。
LengthOfLCIS = 1;
}
max = LengthOfLCIS > max ? LengthOfLCIS : max;
}
return max;
}
};
#endif
class Solution { // 双指针
public:
int findLengthOfLCIS(vector<int>& nums) {
int left=0,right = 0;
int max = 1;
for(int i = 0;i< nums.size()-1; i++){
right++;
if(nums.at(i+1)<=nums.at(i)) {
max = (right-left) > max ? (right-left) : max;
left=right;
}
}
max = (right - left + 1) > max ? (right - left + 1) : max; //最后一次判断是否右指针和左指针的差距是否比max 大,最后一次判断时,右指针和左指针之间的距离需要加1才是所需的长度。
return max ;
}
};
这篇关于leetcode 674 最长连续递增序列 C/C++ 动态规划,动态规划空间优化,双指针 三种解法,初识动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!