All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Roses in a shop
/

Algorithms, Dynamic Programming

Problem
Editorial
Analytics

There are \(n\) roses in a shop. Each rose is assigned an ID. These roses are arranged in order \(1,\ 2,\ 3,\ ... ,\ n\). Each rose has a smell factor denoted as \(smell[i]\) (\(1 \le i \le n \)). You want to buy roses from this shop under the condition that you can buy roses in a segment. In other words, you can purchase roses from \(l\) to \(r\) (\(1 \le l \le r \le n \)). You can remove at most one rose from this segment of roses. Thus, the final length of roses is \(n-1\) or \(n\).

Your task is to calculate the maximum possible length of the strictly-increasing contiguous subarray of the smell factors of these roses.

Note: A contiguous subarray \(a\) with indices from \(l\) to \(r\) is \(a[l,\ ...,\ r]=a[l],\ a[l+1] ,\ ...,\ a[r]\). The subarray \(a[l,\ ...,\ r]\) is strictly increasing if \(a[l]<a[l+1]<\ ...\ <a[r]\).

Input format

  • The first line contains a single integer \(n\) denoting the number of roses that are available in the shop.
  • The second line contains \(n\) space-separated integers \(smell[1],\ smell[2],\ ... ,\ smell[n]\).

Output format

Print one integer denoting the maximum possible length of the strictly-increasing contiguous subarray of the smell factor after removing at most one element.

Constraints

\(2 \le n \le 2\times 10^5 \\ 1 \le smell[i]  \le 10^9\)

SAMPLE INPUT
5
1 2 5 3 4
SAMPLE OUTPUT
4
Explanation

In this case, you can get the maximum length by removing the 3rd element.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?