Summary

Given a sequence \(H\), we want to construct a sequence \(H'\) consisting of non-negative integers such that the absolute difference between any two adjacent elements is exactly \(1\). The goal is to find the maximum number of elements whose original values can be preserved (i.e., \(H'_i = H_i\)).

Analysis

1. Parity Condition

Since the absolute difference between adjacent elements is exactly \(1\), there is a strong constraint on the parity of the index \(i\) and the height \(H'_i\). Specifically, since \(H'_{i+1} = H'_i \pm 1\), the parity of the height must flip whenever the index increases by \(1\).

Therefore, for all \(1 \le i \le N\), there must exist a constant \(C \in \{0, 1\}\) such that: $\(H'_i \equiv i + C \pmod 2\)\( For any point \)i\( where we preserve the original height (i.e., \)H’_i = H_i\(), it must also satisfy \)H_i \equiv i + C \pmod 2$.

From this, we can see that we can solve the problem independently for the cases \(C = 0\) and \(C = 1\), and then take the maximum of the two results.

2. Conditions for Preserved Points

Let us consider the condition under which we can preserve the original heights at two indices \(i < j\) (i.e., setting \(H'_i = H_i\) and \(H'_j = H_j\)). Since the absolute difference between adjacent elements is \(1\), the following inequality must hold for any \(i < j\): $\(|H'_j - H'_i| \le j - i\)\( Conversely, if we select a set of points that satisfies this condition (along with the parity condition), we can always interpolate between them to construct the sequence \)H’\( such that the difference is exactly \)1\( and all elements are non-negative (since the original heights \)H_i\( are non-negative, the values will never drop below \)0$ during the interpolation).

Therefore, the problem reduces to finding the maximum size of a set of indices \(S\) that satisfies the following condition: - For any \(i, j \in S\) (\(i < j\)), \(|H_j - H_i| \le j - i\) holds.

3. Rewriting the Condition (Reduction to 2D)

The absolute value inequality \(|H_j - H_i| \le j - i\) can be expanded into the following two inequalities: 1. \(H_j - H_i \le j - i \iff i - H_i \le j - H_j\) 2. \(-(H_j - H_i) \le j - i \iff H_i + i \le H_j + j\)

Now, for each checkpoint \(i\), we define its coordinates \((x_i, y_i)\) on a 2D plane as follows: - \(x_i = H_i + i\) - \(y_i = i - H_i\)

Then, the condition can be rewritten in a very simple form: - For any \(i, j \in S\) (\(i < j\)), \(x_i \le x_j\) and \(y_i \le y_j\) must hold.

This is equivalent to selecting as many points as possible from the set of 2D points \((x_i, y_i)\) such that they are ordered towards the top-right (or straight up/right). This reduces the problem to finding the Longest Non-Decreasing Subsequence (LNDS).

Algorithm

For each \(C \in \{0, 1\}\), we find the maximum value using the following steps:

1. Extract Points: For each \(i\) satisfying \(H_i \equiv i + C \pmod 2\), calculate the coordinates \((x_i, y_i) = (H_i + i, i - H_i)\) and add them to an array points.
2. Sort: Sort points in ascending order of \(x_i\). If \(x_i\) is equal, sort them in ascending order of \(y_i\).
   • Note: If \(x_i = x_j\), then \(y_i \le y_j\) is automatically satisfied, which means we can select all such points simultaneously. Sorting \(y_i\) in ascending order ensures that the LNDS calculation can correctly select all multiple points that share the same \(x\)-coordinate.
3. Compute LNDS: Find the length of the Longest Non-Decreasing Subsequence (LNDS) of the \(y\)-coordinates of the sorted points.
   • Similar to the standard LIS (Longest Increasing Subsequence), this can be efficiently computed using dynamic programming (DP) with binary search (e.g., std::upper_bound in C++).

The maximum of the LNDS lengths obtained for \(C = 0\) and \(C = 1\) is the final answer.

Complexity

• Time Complexity: \(O(N \log N)\)

  • \(O(N)\) to check parity and calculate coordinates.
  • \(O(N \log N)\) to sort the points.
  • \(O(N \log N)\) to compute the LNDS (DP with binary search).
  • Since we perform these steps twice (once for \(C=0\) and once for \(C=1\)), the overall time complexity is \(O(N \log N)\), which is fast enough for the constraint \(N \le 2 \times 10^5\).

• Space Complexity: \(O(N)\)

  • The size of the array storing the points and the DP table is at most \(N\), so the space complexity is \(O(N)\).

Implementation Details

• Using std::upper_bound: To find the longest non-decreasing subsequence (which allows duplicate values), we use std::upper_bound instead of std::lower_bound for the binary search. This allows us to select multiple points with the same \(y\)-coordinate (e.g., adjacent points in the original sequence with a height difference of exactly \(1\)).

• Preventing Overflow: Since \(H_i \le 10^9\) and \(N \le 2 \times 10^5\), the coordinate \(x_i = H_i + i\) will not exceed \(2^{31}-1\). However, to be safe, it is recommended to use 64-bit integers (long long in C++) for the calculations.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solve_for_C(int N, const vector<long long>& H, int C) {
    vector<pair<long long, long long>> points;
    for (int i = 1; i <= N; ++i) {
        if (H[i - 1] % 2 == (i - 1 + C) % 2) {
            long long x = H[i - 1] + i;
            long long y = i - H[i - 1];
            points.push_back({x, y});
        }
    }
    
    // Sort primarily by x, and secondarily by y
    sort(points.begin(), points.end());
    
    // Find the Longest Non-Decreasing Subsequence (LNDS) on y
    vector<long long> dp;
    for (const auto& p : points) {
        long long val = p.second;
        auto it = upper_bound(dp.begin(), dp.end(), val);
        if (it == dp.end()) {
            dp.push_back(val);
        } else {
            *it = val;
        }
    }
    return dp.size();
}

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    if (!(cin >> N)) return 0;
    
    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    
    int ans = max(solve_for_C(N, H, 0), solve_for_C(N, H, 1));
    cout << ans << "\n";
    
    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.