题意:
思路:
考虑离散化:
枚举 $ x $ 中出现的每一个数 $ val $ , $ val $ 出现的次数为 $ cnt $ ,记录 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ 。设 $ x $ 中与 $ val $ 相等的数贡献为 $ +1 $ ,与 $ val $ 不相等的数贡献为 $ -1 $ ,那么问题转化为最大连续子段和。
由于已经知道 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ ,设区间初始左端点 $ l = idx_1 $ ,区间初始右端点 $ r = idx_1 $ ,最大连续子段和 $ ans = 1 $ ,$ for \space i : 2 \to cnt - 1 $ 枚举每个区间右端点 $ r = idx_i $ ,当区间 $ [l,r] $ 贡献为 $ sum \le 0 $ 时,更新区间左端点为 $ l = idx_i $ ;否则,继续统计区间贡献 $ sum $ , $ ans = max(ans, sum) $ 。
对 $ x $ 中出现的每一个数 $ val $ 进行上述过程即可。
标签:CF1692H,le,val,idx,题解,cnt,端点,区间,Gambling From: https://www.cnblogs.com/ShawyYum/p/17873870.html