题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
#include <iostream> #include <vector> #include <stack> using namespace std; int main() { int n; while (cin >> n) { vector<int> heights; for (int i = 0; i < n; i++) { int num; cin >> num; heights.push_back(num); } int count = 0; vector<int> dp1(n,0); //左侧最长递增子序列长度 for (int i = 0; i < n; i++) { dp1[i] = 1; // 初始化为1 for (int j = 0; j < i; j++) if (heights[j] < heights[i]) dp1[i] = max(dp1[i], dp1[j] + 1); } //右侧最长递增子序列 vector<int> dp2(n,0); for (int i = n-1; i >=0 ; i--) { dp2[i] = 1; // 初始化为1 for (int j = n-1; j > i; j--) if (heights[j] < heights[i]) dp2[i] = max(dp2[i], dp2[j] + 1); } for (int i = 0; i <n; i++) count = max(count, dp1[i] + dp2[i] - 1); // 减去重复计算的i位置 cout << n- count << endl; } return 0; }