本文共 2309 字，大约阅读时间需要 7 分钟。

题目来源：

Description

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<al+1<⋯<ar.

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.

Sample Input

5

Sample Output

4

解题思路:

• 第一种方法：

  分别记录第i个数前面的递增个数和后面的递增个数，
  最后遍历所有的i，因为只有两种情况值最大：
  1. 第i个的递增个数
  2. 当arr[i-1]<arr[i+1]时，不要第i个时（i-1）前面的递增个数 + （i+1）后面的递增个数。

• 第二种方法

  通过两个dp数组分别存第i个的递增个数和记录最大情况。（详情看下方代码）

AC代码：

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'using ll = long long;const int MAXN = 2e5+5;int dp[2][MAXN],arr[MAXN];int main(){
       SIS;    int n,ans=0;    cin >> n;    for(int i=1;i<=n;i++)    {
           cin >> arr[i];        if(arr[i]>arr[i-1]) dp[0][i]=dp[0][i-1]+1;        else dp[0][i]=1;    }    for(int i=n;i>0;i--)    {
           if(arr[i+1]>arr[i]) dp[1][i]=dp[1][i+1]+1;        else dp[1][i]=1;    }    for(int i=1;i<=n;i++)    {
           ans=max(ans,dp[1][i]);        if(arr[i-1]
   

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'const int MAXN = 2e5+5;int dp[2][MAXN],arr[MAXN];int main(){
       SIS;    int n,ans=0;    cin >> n;    for(int i=1;i<=n;i++) cin >> arr[i];    dp[0][1]=dp[1][1]=1;    for(int i=2;i<=n;i++)    {
           if(arr[i]>arr[i-1])        {
               dp[0][i]=dp[0][i-1]+1;            dp[1][i]=dp[1][i-1]+1;        }        else dp[0][i]=dp[1][i]=1;        if(arr[i]>arr[i-2])            dp[1][i]=max(dp[1][i],dp[0][i-2]+1);    }    for(int i=1;i<=n;i++)        ans=max(ans,max(dp[0][i],dp[1][i]));    cout << ans << endl;    return 0;}
   

转载地址：http://msyof.baihongyu.com/