Codeforces Round #605 (Div. 3) D. Remove One Element You are given an array a consisting of n integers.
You can remove at most one element from this array. Thus, the final length of the array is n?1 or n.
Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.
Recall that the contiguous subarray a with indices from l to r is a[l…r]=al,al+1,…,ar. The subarray a[l…r] is called strictly increasing if al
Input The first line of the input contains one integer n (2≤n≤2?105) — the number of elements in a.
The second line of the input contains n integers a1,a2,…,an (1≤ai≤109), where ai is the i-th element of a.
Output Print one integer — the maximum possible length of the strictly increasing contiguous subarray of the array a after removing at most one element.
Examples
input
5
1 2 5 3 4
output
4
input
2
1 2
output
2
input
7
6 5 4 3 2 4 3
output
2
【Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element】这题比赛咋都写不出来,看了题解傻了,用两个数组记录一下就可以了,l记录从i到n-1的连续严格递增序列的长度,r记录从0到i的连续严格递增序列的长度,然后就很简单了,cf真的灵活啊,脑洞炸裂/(ㄒoㄒ)/~~
#include
using namespace std;
typedef long long ll;
int a[200005],l[200005],r[200005];
int main()
{
int n,ans=1;
cin>>n;
for(int i=0;
i>a[i];
l[i]=r[i]=1;
}
for(int i=n-1;
i>=1;
i--){
if(a[i]>a[i-1]) l[i-1]=l[i]+1;
ans=max(ans,l[i-1]);
}
for(int i=0;
i
推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析(Java实现)—— 动态规划 (0-1 背包问题)
- 动态规划|暴力递归经典问题
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock