今日学习记录
1. 3738. 替换至多一个元素后最长非递减子数组
关键词：前缀和
问题分析：
至多改变数组中任意位置的数一次,让数组中的不严格递增序列最大
核心思路: 这个题非常简单,但是边界依旧是这种单调序列的难点 其次就是我们要选出一个地方,他可能使两个单调序列连在一起 其余的直接加一
前后缀和
使两个单调序列连接,我们直接枚举分割点就行了,那么分割点的左右就是要预处理的最长单调序列长度,使用前后缀来处理
**最终代码：
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int n = nums.size();
if(n<=1) return n;
vector<int> pre(n,1),suf(n,1);
for(int i = 0;i<n-1;i++) if(nums[i]<=nums[i+1]) pre[i+1] = pre[i]+1;
for(int i = n-2;i>=0;i--) if(nums[i]<=nums[i+1]) suf[i] = suf[i+1]+1;
int ans = 1;
for(int i = 0;i<n;i++){
ans = max({ans,pre[i],suf[i]});
if(i<n-1&&i>0&&nums[i-1]<=nums[i+1]){
ans = max(ans,pre[i-1]+suf[i+1]+1);
}else{
if(i+1<n) ans = max(ans,suf[i+1]+1);
if(i-1>=0) ans = max(ans,pre[i-1]+1);
}
}
return ans;
}
};