Advertisement
Guest User

Untitled

a guest
Feb 10th, 2016
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAXN 100005
  3.  
  4. using namespace std;
  5.  
  6. int a[MAXN], n, fst, sec, maxx, minn, maxI, tr, Imaxx, Iminn;
  7.  
  8. int main()
  9. {
  10. scanf("%d", &n);
  11. for (int i = 0; i < n; i++)
  12. scanf("%d", &a[i]);
  13.  
  14. fst = 0; // prvi ukljucen u trenutnu sesiju
  15. sec = 1; // prvi sledeci ukljucen u narednu sesiju
  16. maxI = 1; // maksimalna validna sesija
  17. tr = 1; // trenutna duzina sesije
  18. minn = a[0]; // minimum trenutne sesije
  19. maxx = a[0]; // maksimum trenutne sesije
  20. Imaxx = 0; // poslednji indeks u sesiji gde se pojavljuje trenutni minn
  21. Iminn = 0; // poslednji indeks u sesiji gde se pojavljuje trenutni maxx
  22.  
  23. while (sec != n)
  24. {
  25. if (a[sec] == minn || (minn == maxx && a[sec] == maxx - 1)) // sledeci koji se treba ubaciti u segment je vrednost minn
  26. {
  27. minn = a[sec];
  28. Iminn = sec;
  29. tr++;
  30. sec++;
  31. if (maxI < tr)
  32. maxI = tr;
  33.  
  34. if (maxx == minn)
  35. Imaxx = Iminn;
  36. }
  37. else
  38. {
  39. if (a[sec] == maxx || (minn == maxx && a[sec] == minn + 1)) // sledeci koji se treba ubaciti u segment je vrednost maxx
  40. {
  41. maxx = a[sec];
  42. Imaxx = sec;
  43. tr++;
  44. sec++;
  45. if (maxI < tr)
  46. maxI = tr;
  47.  
  48. if (maxx == minn)
  49. Iminn = Imaxx;
  50. }
  51. else // sledeci koji se treba ubaciti u segment je razliciti i od minn i od maxx
  52. {
  53. if (fst == Iminn && minn != maxx) // izbacuje se poslednji minn; minn != maxx
  54. {
  55. if (a[sec] == maxx + 1) // ako a[sec] treba da postane novi maxx
  56. {
  57. minn = maxx;
  58. Iminn = Imaxx;
  59. maxx = a[sec];
  60. Imaxx = sec;
  61. sec++;
  62. fst++;
  63. }
  64. else // sledeca sesija ce poceti od sec
  65. {
  66. maxx = minn = a[sec];
  67. Imaxx = Iminn = sec;
  68. fst = sec;
  69. sec++;
  70. tr = 1;
  71. }
  72. }
  73. else
  74. {
  75. if (fst == Imaxx && minn != maxx) // izbacuje se poslednji maxx; minn != maxx
  76. {
  77. if (a[sec] == minn - 1) // ako a[sec] treba da postane novi minn
  78. {
  79. maxx = minn;
  80. Imaxx = Iminn;
  81. minn = a[sec];
  82. Iminn = sec;
  83. sec++;
  84. fst++;
  85. }
  86. else // sledeca sesija ce poceti od sec
  87. {
  88. maxx = minn = a[sec];
  89. Imaxx = Iminn = sec;
  90. fst = sec;
  91. sec++;
  92. tr = 1;
  93. }
  94. }
  95. else // ( maxx == minn && Imaxx = Iminn == fst ) ili se ne izbacuju ni minn ni maxx --> sledeca sesija pocinje od sec
  96. {
  97. maxx = minn = a[sec];
  98. Imaxx = Iminn = sec;
  99. fst = sec;
  100. sec++;
  101. tr = 1;
  102. }
  103. }
  104. }
  105. }
  106. }
  107.  
  108. printf("%d\n", maxI);
  109.  
  110. return 0;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement