Guest User

Untitled

a guest
Dec 12th, 2018
538
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define MOD 1000000007
  4. #define pb push_back
  5. #define mp make_pair
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef unsigned long long ull;
  11.  
  12. int dp[1000005][3],N;
  13. ll A[1000005];
  14.  
  15. int f(int i,int state){
  16. if(i>N)
  17. return 0;
  18. else if(dp[i][state]!=-1){
  19. return dp[i][state];
  20. }
  21. else{
  22. if(i==N)
  23. dp[i][state]=1;
  24. else if(state==1 && A[i]>A[i+1])
  25. dp[i][state]=1;
  26. else if(state==2 && A[i]<A[i+1])
  27. dp[i][state]=1;
  28. else if(state==1 && A[i]<=A[i+1])
  29. dp[i][state]=1+f(i+1,2);
  30. else if(state==2 && A[i]>=A[i+1])
  31. dp[i][state]=1+f(i+1,1);
  32. return dp[i][state];
  33. }
  34. }
  35.  
  36. int main(){
  37.  
  38. //freopen("1.in","r",stdin);
  39. //freopen("1.out","w",stdout);
  40.  
  41. int T,i,x,ans;
  42. cin>>T;
  43. while(T--){
  44. memset(dp,-1,sizeof dp);
  45. cin>>N;
  46. for(i=1;i<=N;i++){
  47. cin>>A[i];
  48. }
  49. for(i=1;i<=N;i++){
  50. x=f(i,1);
  51. //cout<<i<<" "<<x<<" ";
  52. x=f(i,2);
  53. //cout<<x<<"\n";
  54. }
  55. ans=-1;
  56. for(i=1;i<=N;i++){
  57. x=dp[i][1];
  58. if(i+x>N)
  59. ans=max(ans,dp[i][1]+1);
  60. else if(x%2==0)
  61. ans=max(ans,dp[i][1]+1+dp[i+x][2]);
  62. else if(x%2==1)
  63. ans=max(ans,dp[i][1]+1+dp[i+x][1]);
  64. }
  65. cout<<ans<<"\n";
  66. }
  67. return 0;
  68. }
Add Comment
Please, Sign In to add comment