最长递增子序列

计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得Ti<T2<......<Ti-1<Ti>Ti+1>......>TK。 
     你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 

整数N

一行整数，空格隔开，N位同学身高

最少需要几位同学出列

8

186 186 150 200 160 130 197 200

               </pre></td></tr><tr><td class="grid_left_td">样例输出:</td><td><pre>4

                </pre></td></tr></tbody></table>

根据题意可知，我们需要求出一个“中间点”，使得其左边的【最长递增子序列】和其右边的【最长递减子序列】之和最大。

    #include <iostream>  
    #include <vector>  
    using namespace std;  
      
    int LonggestIncreaseLength(vector<int> &vec) {  
        vector<int> result(vec.size(), 1);  
        vector<int> result2(vec.size(), 1);  
        for (int i = 1; i < vec.size(); i++) {  
            for (int j = 0; j < i; j++) {  
                if (vec[i] > vec[j] && result[i] < result[j] + 1)  
                    result[i] = result[j] + 1;  
            }  
        }  
      
        for (int i = vec.size() - 2; i >= 0; --i) {  
            for (int j = vec.size() - 1; j > i; --j) {  
                if (vec[i] > vec[j] && result2[i] < result2[j] + 1)  
                    result2[i] = result2[j] + 1;  
            }  
        }  
        int max = 0;  
        for (int i = 0; i < vec.size(); i++) {  
            if (max < result[i] + result2[i])  
                max = result[i] + result2[i];  
        }  
        return vec.size() - max + 1;  
    }  
    int main() {  
        int n;  
        cin >> n;  
        if (n <= 0)  
            return 0;  
        vector<int> ivec(n);  
        for (int i = 0; i < n; i++)  
            cin >> ivec[i];  
        cout << LonggestIncreaseLength(ivec) << endl;  
    }