题解 | 可恶的墨水

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int m = n - 1;
        vector<int> a(m);
        for (int i = 0; i < m; i++) {
            cin >> a[i];
        }
        
        int ans = 1;
        
        // dp1[i]: 以a[i]结尾的最长连续递增段长度
        vector<int> dp1(m, 1);
        for (int i = 1; i < m; i++) {
            if (a[i-1] + 1 == a[i]) {
                dp1[i] = dp1[i-1] + 1;
            }
            ans = max(ans, dp1[i]);
        }
        
        // dp2[i]: 以a[i]开头的最长连续递增段长度
        vector<int> dp2(m, 1);
        for (int i = m-2; i >= 0; i--) {
            if (a[i] + 1 == a[i+1]) {
                dp2[i] = dp2[i+1] + 1;
            }
            ans = max(ans, dp2[i]);
        }
        
        // 缺失数放在开头
        if (a[0] > 1) {
            ans = max(ans, dp2[0] + 1);
        }
        
        // 缺失数放在结尾
        if (a[m-1] < n) {
            ans = max(ans, dp1[m-1] + 1);
        }
        
        // 缺失数放在中间
        for (int i = 0; i < m-1; i++) {
            if (a[i] + 2 == a[i+1]) {
                // 正好缺中间一个数，可以连接两段
                ans = max(ans, dp1[i] + dp2[i+1] + 1);
            } else {
                // 不能连接，取两段中较长的一段，加1（把缺失数放在这段边上）
                ans = max(ans, max(dp1[i], dp2[i+1]) + 1);
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}