题解

问题理解

给定一个序列 a，要选择一个长度至少为 2 的连续子区间 [l, r]，使得区间内最大值减去最小未出现非负整数 (MEX) 的值最大。

关键结论

最优区间一定可以取长度为 2 的相邻子区间。理由如下：

  • 若某个最优区间的 MEX = 0，说明区间内不含 0。此时取该区间内最大值所在的元素，再任选一个相邻元素（仍不含 0）组成长度为 2 的子区间，其 MEX 仍为 0，最大值不变，差值相同。
  • 若 MEX = k > 0，则区间内必然包含 0,1,...,k-1，且最大值至少为 k。可以证明，一定存在一个相邻对（如最大值和 0，或最大值和某个小数字）使得其差值不小于原区间差值。
  • 因此，只需检查所有相邻位置对 (i, i+1) 即可。

算法步骤

  1. 初始化答案为一个很小的负数。
  2. 遍历 i 从 0 到 n-2： 设 x = a[i], y = a[i+1]区间最大值 maxn = max(x, y)计算两个数的 MEX： 若 0 不在 {x, y} 中，则 MEX = 0 否则若 1 不在，则 MEX = 1 否则 MEX = 2更新答案 ans = max(ans, maxn - mex)
  3. 输出答案。

复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

示例代码（Java）

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            int[] a=new int[n];
            for(int i=0;i<n;i++) a[i]=in.nextInt();
            int ans=-0x3f3f3f3f;
            for(int i=0;i<n-1;i++){
                int mex=0;
                int maxn=a[i]>a[i+1]?a[i]:a[i+1];
                while(mex==a[i]||a[i+1]==mex) ++mex;
                if(ans<maxn-mex) ans=maxn-mex;
            }
            System.out.println(ans);
        }
    }
}