给定一个长度为 的正整数数组 ,每个元素代表一道题目的难度。你可以执行最多 次修改操作,每次操作可以选择数组中的任意一道题目并将其难度修改为任意正整数。
你的目标是通过这些修改,使得数组中存在一个尽可能长的连续子数组,满足该子数组内相邻两个元素的差值恰好为 。也就是说,若选定的连续子数组为 ,则对于所有的 ,必须满足 。
请输出在最优策略下,满足上述条件的最长连续子数组的长度。
第一行包含两个整数 和 (),分别表示数组长度和最大修改次数。
第二行包含 个以空格分隔的正整数 ()。
输出一个整数,表示修改后能得到的最长连续公差为 的子数组的长度。
6 2 2 5 4 5 8 9
5
我们可以通过 2 次修改将数组变成:[2, 3, 4, 5, 6, 9](将第 2 个元素从 5 改为 3,将第 5 个元素从 8 改为 6)。
[2, 3, 4, 5, 6, 9]
此时前 5 个元素组成的连续子数组 [2, 3, 4, 5, 6] 满足相邻差值为 1,长度为 5。可以证明无法通过 2 次修改获得长度为 6 的合法子数组。
[2, 3, 4, 5, 6]