根据题意,考虑先相邻的数两两相减,计算差分数组(也就是增量数组)。
接下来问题变成求差分数组中最长的相等段。这个可以考虑用双指针获取。具体看代码实现~
两位运动员参加为期 n 天的集训,每天都会获得一个整数评分。教练发现,如果某一天两人相比于前一天的评分变化量不同,他们就会在训练中产生不必要的较量;若变化量相同,则当天相安无事。特别地,集训的第一天由于没有前一天的参考,两人不会互相较量。
具体来说,设第 i 天运动员 A 的评分为 ai,运动员 B 的评分为 bi。对于 1≤i<n,称 di=ai+1−ai 和 ei=bi+1−bi 分别为两人在第 i 天到第 i+1 天的变化量。若 dieqei,则第 i+1 天会发生较量;若 di=ei,则相安无事。
教练希望选出一段连续的天数 [L,R](1≤L≤R≤n),使得在这段训练日内,每一天都不会发生较量。请求出能够选择的最多天数。
约束:集训天数 n 满足 2≤n≤105,每天的评分绝对值不超过 109,即 ∣ai∣≤109,∣bi∣≤109。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册