fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. /*  function to returns minimum removals needed
  4.  to make a mountain array */
  5. int minMountainRemovals(vector<int> &a)
  6. {
  7.     /*  Declaring two dp vectors to store the maximum result for any indexing
  8.         from left and right respectively */
  9.     int n = a.size();
  10.     vector<int> dpleft(a.size(), 1);
  11.     vector<int> dpright(a.size(), 1);
  12.     // vector<int> dpleft,dpright;
  13.  
  14.     /* declaring temporary vector lis
  15.     it will help us to fill dpleft and dpright in nlongn complexity */
  16.     vector<int> lis;
  17.     // filing dpleft using lis in nlogn
  18.     for (int i = 0; i < n; i++)
  19.     {
  20.         auto it = lower_bound(lis.begin(), lis.end(), a[i]);
  21.         // if element is to be inserted in lis
  22.         if (it != lis.end())
  23.         {
  24.             int idx = it - lis.begin();
  25.             lis[idx] = a[i];
  26.             dpleft[i] = idx + 1;
  27.         }
  28.         // if element in not present in lis insert at the end
  29.         else
  30.         {
  31.             lis.push_back(a[i]);
  32.             dpleft[i] = lis.size();
  33.         }
  34.     }
  35.  
  36.     // clearing lis vector to use to calculate right lis
  37.     lis.clear();
  38.     // reversing the original vector to calculate lis from back
  39.     reverse(a.begin(), a.end());
  40.  
  41.     // filling dpright
  42.     for (int i = 0; i < n; i++)
  43.     {
  44.         auto it = lower_bound(lis.begin(), lis.end(), a[i]);
  45.         if (it != lis.end())
  46.         {
  47.             int idx = it - lis.begin();
  48.             lis[idx] = a[i];
  49.             dpright[i] = idx + 1;
  50.         }
  51.         // if element in not present in lis insert at end
  52.         else
  53.         {
  54.             lis.push_back(a[i]);
  55.             dpright[i] = lis.size();
  56.         }
  57.     }
  58.     int longest = 0;
  59.  
  60.     // for every index check for longest mountain array,
  61.     for (int i = 1; i < a.size() - 1; i++)
  62.     {
  63.         if (dpleft[i] >= 1 && dpright[i] >= 1)
  64.         {
  65.             int ans = dpleft[i] + dpright[i] - 1;
  66.             longest = max(longest, ans);
  67.         }
  68.     }
  69.     // returning removals
  70.     return a.size() - longest;
  71. }
  72. int main()
  73. {
  74.     int n;
  75.     cin >> n;
  76.     // taking input for array size
  77.     vector<int> a(n, 0);
  78.     // Taking array input as vector
  79.     for (int i = 0; i < n; i++)
  80.     {
  81.         cin >> a[i];
  82.     }
  83.  
  84.     // calling minMountainRemovals function to return minimum number of       removals
  85.     int removals = minMountainRemovals(a);
  86.     cout << removals << endl;
  87.     return 0;
  88. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6
2 3 0 5 1 4
stdout
copy 
3
https://ideone.com/poD3xb
language:
C++ (gcc 8.3)
created:
23 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!