Advertisement
pasholnahuy

Biggest monotonic subsequence

Mar 5th, 2024
600
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. pair<int, int> BiggestIncreasingSubs(const vector<int>& arr){
  7.     int l = -1;
  8.     int r = -1;
  9.     int biggest_len = 0;
  10.     int cur_l = 0;
  11.     for (int i = 0; i < arr.size() - 1; ++i){
  12.         if (arr[i] > arr[i+1]){
  13.             if (i - cur_l + 1 > biggest_len){
  14.                 l = cur_l;
  15.                 r = i;
  16.                 biggest_len = i - cur_l + 1;
  17.             }
  18.             cur_l = i + 1;
  19.         }
  20.     }
  21.     if (arr.size() - cur_l > biggest_len){
  22.         l = cur_l;
  23.         r = arr.size() - 1;
  24.     }
  25.     return {l, r};
  26. }
  27.  
  28. int main() {
  29.     int n;
  30.     cin >> n;
  31.     vector<int> v(n);
  32.     for (int i = 0; i < n; ++i) {
  33.         cin >> v[i];
  34.     }
  35.     auto ans1 = BiggestIncreasingSubs(v);
  36.     reverse(v.begin(), v.end());
  37.     auto ans2 = BiggestIncreasingSubs(v);
  38.     if (ans1.second - ans1.first > ans2.second - ans1.first){
  39.         cout << ans1.first << " " << ans1.second;
  40.     } else {
  41.         cout << v.size() - 1 - ans2.second << " " << v.size() - ans1.first - 1;
  42.     }
  43.     return 0;
  44. }
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement