| Codeforces Round 1135 (Div. 2) |
|---|
| Finished |
You are given an array $$$a$$$ of length $$$n$$$ and a positive integer $$$k$$$.
A subarray$$$^{\text{∗}}$$$ $$$a[l..r]$$$ is called an arithmetic subarray if the difference between consecutive elements is constant; that is, $$$$$$a_{l+1} - a_l = a_{l+2} - a_{l+1} = \ldots = a_r - a_{r-1}.$$$$$$ Note that all subarrays of length one are arithmetic.
You are allowed to choose at most $$$k$$$ elements of $$$a$$$ and change them to any integers (not necessarily in $$$[1,10^9]$$$) of your choice. Your task is to find the maximum possible length of an arithmetic subarray of $$$a$$$ after these changes.
$$$^{\text{∗}}$$$A subarray of $$$a$$$ is the array $$$[a_l,a_{l+1},\ldots a_r]$$$ for some $$$1\le l\le r\le n$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le \min(n, 1500)$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$. It is guaranteed that the sum of $$$n\cdot k$$$ across all test cases does not exceed $$$10^7$$$.
For each test case, output a single integer — the maximum possible length of an arithmetic subarray of $$$a$$$ after changing at most $$$k$$$ elements of $$$a$$$.
45 11 2 6 4 55 11 2 3 100 2003 11 1000000000 26 21 2 4 8 16 32
5434
In the first test case, the answer of $$$5$$$ can be achieved by $$$a=[1,2,3,4,5]$$$.
In the third test case, the answer of $$$3$$$ can be achieved by $$$a=[1\,999\,999\,998,1\,000\,000\,000,2]$$$.
| Name |
|---|


