计算选择性删除元素后序列的最长连续上升子序列长度的代码实现

本题的思路是先分别计算以每个元素结尾的最长连续上升子序列的长度和以每个元素开头的最长连续上升子序列的长度，然后根据这些信息找出删除最多一个元素后的最长连续上升子序列的长度。 以下是完整的代码实现及详细 ```cpp #include<bits/stdc++.h> using namespace std; // a 数组用于存储输入的序列，f 数组用于存储以每个元素结尾的最长连续上升子序列的长度 // g 数组用于存储以每个元素开头的最长连续上升子序列的长度 int a[200005], f[200005], g[200005]; int n, ans; int main () { cin >> n; // 读取输入的序列 for (int i = 1; i <= n; i++) cin >> a[i]; // f[i]:以 a[i] 结尾的最长连续上升子序列 f[1] = 1; // 计算以每个元素结尾的最长连续上升子序列的长度 for (int i = 2; i <= n; i++) { // 如果当前元素大于前一个元素，则最长连续上升子序列长度加 1 if (a[i] > a[i - 1]) { f[i] = f[i - 1] + 1; } else { // 否则，最长连续上升子序列长度为 1 f[i] = 1; } } // g[i]:以 a[i] 开头的最长连续上升子序列 g[n] = 1; // 计算以每个元素开头的最长连续上升子序列的长度 for (int i = n - 1; i >= 1; i--) { // 如果当前元素小于后一个元素，则最长连续上升子序列长度加 1 if (a[i] < a[i + 1]) { g[i] = g[i + 1] + 1; } else { // 否则，最长连续上升子序列长度为 1 g[i] = 1; } } // 不删除元素的情况，找出 f 数组中的最大值 for (int i = 1; i <= n; i++) { ans = max(ans, f[i]); } // 删除一个元素的情况 for (int i = 2; i < n; i++) { // 如果 a[i - 1] < a[i + 1]，则可以将 a[i] 删除，更新最长连续上升子序列的长度 if (a[i - 1] < a[i + 1]) { ans = max(ans, f[i - 1] + g[i + 1]); } } cout << ans; return 0; } ``` ######[AI问答 | 696点数解答 | 2026-08-15 20:42:49]