闫式dp 分析法

/*
    /*

    题目分析 :
                1) 这题和上一题差不多我就不做过多的分析了

                2) 求一下f[i] 这个点的  最长上升子序列 + 最长下降子序列 的最大值

                3) 注意点  : 3 - 1）最后结果为 g[i] + f[i] - 1 , 因为i这个点被计算了两次 

                            3 - 2）n - res 最后结果
*/



*/


#include <iostream>
#include <algorithm>
#include <cstring>

using namespace  std;
const int N = 1010;
int h[N] , g[N] , f[N];

int n;
int main() {

    cin >> n;
    for (int i = 1 ; i <= n ; i ++ ) cin >> h[i];

    for (int i = 1 ; i <= n  ;i ++ ) {
        f[i] = 1;
        for (int j = 1 ; j < i ; j ++ )
            if (h[i] > h[j]) f[i] = max(f[i] , f[j] + 1);
    }
    for (int i = n ; i >= 1 ; i --) {
        g[i] = 1;
        for (int j = n ; j > i ; j --) 
            if (h[i] > h[j]) g[i] = max(g[i] , g[j] + 1);
    }

    int res = 0;
    for (int i = 1 ; i <= n ; i ++ ) res = max(res , f[i] + g[i] - 1);
    cout << n - res;
    return 0;
}