NC155. 最长严格上升子数组(一)
描述
示例1
输入:
[7,2,3,1,5,6]
输出:
5
说明:
将1改为4，最长严格上升子数组为[2,3,4,5,6]示例2
输入:
[1,2,3,4]
输出:
4
说明:
最长严格上升子数组为[1,2,3,4]示例3
输入:
[1,2,2,3]
输出:
3
说明:
改变一个元素之后，最长严格上升子数组为[1,2,3]或者[2,3,4]，长度都为3C++ 解法, 执行用时: 18ms, 内存消耗: 3256KB, 提交时间: 2022-01-09
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxSubArrayLengthTwo(vector<int>& nums) {
// write code here
int len = nums.size();
vector<int> head(len,1);
vector<int> tail(len,1);
for(int i=1; i<len;i++){
if(nums[i] > nums[i-1]){
tail[i] = tail[i-1]+1;
}
else{
tail[i] = 1;
}
}
for(int i=len-2; i>=0;--i){
if(nums[i] < nums[i+1]){
head[i] = head[i+1]+1;
}
else{
head[i] = 1;
}
}
int ans = 1;
for(int i=0; i<len; ++i){
if(i>0 && i<len-1 && nums[i-1] < nums[i+1]-1){
ans = max(ans, tail[i-1]+head[i+1]+1);
}
else if(i>0){
ans = max(ans, tail[i-1]+1);
}
else if(i<len-2 && nums[i+1] > 1){
ans = max(ans, head[i+1]+1);
}
}
return ans;
}
};
C++ 解法, 执行用时: 18ms, 内存消耗: 3256KB, 提交时间: 2021-12-01
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxSubArrayLengthTwo(vector<int>& nums) {
// write code here
int maxLen = 0;
int lastLen = 0;
int start = 0;
for (int i = 0; i < nums.size(); ++i) {
int pre = 0;
if (i > 0) pre = nums[i - 1];
if (nums[i] > pre) {
//len++
maxLen = max(maxLen, i - start + 1 + lastLen);//包含第i位 start-i的长度 加上 前一段的长度
} else {
maxLen = max(maxLen, i - start + (lastLen == 0 ? 1 : lastLen));//处理结束的可能 如果lastlen=0 表示并没有用到修改 可以+1(第i位)
if ((i < nums.size() - 1 && nums[i + 1] - pre > 1) || (i - 2 >= 0 && nums[i] - nums[i - 2] > 1))
{
//能通过修改一个值 num[i] 或者 num[i-1] 连起来
//前一段的长度 i - start
lastLen = i - start;
} else {
//不能完整的连起来
//但是可以修改一个值
//前一段能修改的话 lastlen = 1
lastLen = 1;
if (nums[i] == 1) lastLen = 0;
}
start = i;
}
}
return maxLen;
}
};
C++ 解法, 执行用时: 18ms, 内存消耗: 3264KB, 提交时间: 2021-10-12
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int tail[110000] , head[110000];
int maxSubArrayLengthTwo(vector<int>& nums) {
// write code here
tail[0] = 1;
for (int i = 1 ; i < nums.size() ; i ++) {
if (nums[i] > nums[i-1]) {
tail[i] = tail[i-1] +1;
} else {
tail[i] = 1;
}
}
head[nums.size()-1] = 1;
for (int i = nums.size()-2 ; i >= 0 ; i --) {
if (nums[i] < nums[i+1]) {
head[i] = head[i+1]+1;
} else {
head[i] = 1;
}
}
int res = 1;
for (int i = 0 ; i < nums.size() ; i ++) {
if (nums[i+1] > 1)res = max(res,head[i+1]+1);
if (i > 0) res = max(res,tail[i-1]+1);
if (i > 0 && (nums[i+1]-nums[i-1] >= 2)) res = max(res,head[i+1]+tail[i-1]+1);
}
return res;
}
};
C++ 解法, 执行用时: 18ms, 内存消耗: 3860KB, 提交时间: 2021-10-17
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxSubArrayLengthTwo(vector<int>& nums) {
// write code here
int size = nums.size();
if(size <= 2) return size;
int maxv = 1;
int left[size];
int right[size];
for (int i = 0; i < size; i++){
left[i] = 1;
right[i] = 1;
if (i > 0 && nums[i] > nums[i - 1]){
left[i] = left[i - 1] + 1;
maxv = max(maxv, left[i]);
}
}
if (maxv == size){//如果res == n即该数组就是严格上升数组，直接返回res即可
return maxv;
}
for (int i = size-1; i >= 0; i--){
if (i < size-1 && nums[i] < nums[i + 1]){
right[i] = right[i + 1] + 1;
}
}
for(int i = 0; i < size; i++) {
if(i == 0){
if(right[i] == 1 && nums[i+1] > 1) {
maxv = max(maxv,right[i+1] + 1);
}
} else if (i == size-1){
if (left[i] == 1 && nums[i-1] < 100000) {
maxv = max(maxv,left[i-1]+1);
}
} else{
if(right[i] == 1){
if(nums[i+1]-nums[i-1] >= 2) {
maxv = max(maxv, left[i] + right[i+1]);
} else {
if(nums[i+1] > 1) {
maxv = max(maxv,right[i+1]+1);
}
}
}
if(left[i] == 1){
if(nums[i+1]-nums[i-1] >= 2) {
maxv = max(maxv, right[i] + left[i-1]);
} else {
if(nums[i-1] < 100000) {
maxv = max(maxv,left[i-1]+1);
}
}
}
}
}
return maxv;
}
};
C++ 解法, 执行用时: 19ms, 内存消耗: 3268KB, 提交时间: 2022-02-14
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxSubArrayLengthTwo(vector<int>& nums) {
// write code here
// dp[2][i]
int len=nums.size();
if(len==1)
return 1;
vector<int> dpLeft(len, 1);
for(int i=1; i<len; ++i)
if(nums[i]>nums[i-1])
dpLeft[i]= dpLeft[i-1]+1;
vector<int> dpRight(len, 1);
for(int i=len-2; i>=0; --i)
if(nums[i]<nums[i+1])
dpRight[i]= dpRight[i+1]+1;
int maxLen=1;
for(int i=0; i<len; ++i){
if(i>0 && i<len-1 && nums[i+1]-nums[i-1]>1)
maxLen=max(maxLen, dpLeft[i-1]+dpRight[i+1]+1);
else{
if(i>0)
maxLen=max(maxLen, dpLeft[i-1]+1);
if(i<len-1 && nums[i+1]>1)
maxLen=max(maxLen, dpRight[i+1]+1);
}
}
return maxLen;
}
};