解题思路
给定长度为 n 的数组 a[1..n]。对任意区间 [l,r]：
- 记编码差为
a[r] - a[l]
- 记
g(l,r) 为区间内不同元素的种类数
- 净余震量：
(a[r] - a[l]) - g(l,r)
目标：在所有 1 ≤ l ≤ r ≤ n 中求最大值。
P3839.第3题-钟阵净余谐振能量
题目内容
钟师在远古祭坛铺设了 n 口钟阵，每口钟的编号记录在数组 {a1,a2,...,an} 中;
对任意区间 [l,r] ，记钟面编号差 △面=ar−al ，并令 g(l,r) 表示区间内不同钟声的种类数;
于是区间的净余谐振能量定义为
△净余=(ar−al)−g(l,r)
请你在所有 1≤l≤r≤n 的区间中，求得最大的 △净余。
输入描述
第一行输入一个整数 n(1≤n≤2×105) ，钟阵长度;
第二行输入 n 个整数 a1,a2,...,an(1≤ai≤n) 表示每口钟的编号。
输出描述
输出一个整数，表示所有区间中最大净余谐振能量。
样例1
输入
5
1 3 1 5 3
输出
2
说明
选择区间 [3,4] ：
样例2
输入
5
1 2 3 4 5
输出
-1
