Summary: Given an array $A$ with $N$ elements. Find the largest continous subbarray $(l,\ r)$ of $A$ that: $max(A_l,\ A_{l + 1},\ ...,\ A_r)\ \vdots\ min(A_l,\ A_{l + 1},\ ...,\ A_r)$. Print the value $r - l + 1$. Cconstraints: $n\leq 6\times 10^5,\ a_i\leq 10^5\\ forall\ 1\leq i\leq n$.↵
↵
Subtasks:↵
↵
- $n\leq 500$ and $n\leq 5000$: for $O(n^2)$.↵
↵
- $a_1\leq a_2\leq ...\leq a_n$: for dp $O(n\ log\ n)$.↵
↵
- $a_i\leq 1000$: dont know how to do.↵
↵
- $n\leq 10^5$: dont know how to do.↵
↵
- No additional constraints: dont know how to do.↵
↵
Please help me with this problem, thanks for your help and attention. Have a good day !
↵
Subtasks:↵
↵
- $n\leq 500$ and $n\leq 5000$: for $O(n^2)$.↵
↵
- $a_1\leq a_2\leq ...\leq a_n$: for dp $O(n\ log\ n)$.↵
↵
- $a_i\leq 1000$: dont know how to do.↵
↵
- $n\leq 10^5$: dont know how to do.↵
↵
- No additional constraints: dont know how to do.↵
↵
Please help me with this problem, thanks for your help and attention. Have a good day !
