It's Midterms week!
Ali has a digital logic design exam for today, and he struggled with the following problem:
Given an array of length $n$ and an integer $k$, find a prefix of the array of length $X$ and a suffix of the array of length $Y$ such that:
Can you help Ali by finding what the maximum possible sum is?
The first line contains one integer $T$ $(1 \le T \le 10^4)$, the number of test cases.
Each test case consists of two lines, the first line contains $n$ the length of the array, and $k$ $(1 \le k \le n \le 2\times 10^5)$.
The second line contains $n$ space-separated integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^4)$ the elements of the array.
It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2\times 10^5$.
The maximum possible sum.
The operator $\oplus$ is the bitwise operator $xor$.
| Input | Output |
|---|---|
3 5 5 1 2 3 4 5 5 2 10 1 2 2 2 5 3 1 1 1 1 1 Copy
|
15 16 3 Copy
|
The idea of the solution is that we are going to brute force the value of $X$, which may be any value between $0$ (empty prefix) and $n$.
Then we can find $Y$ easily by finding the value of $X \oplus n$.
That’s one of the properties of the $xor$ operator, if we have three integers such that $A \oplus B = C$, and we know $A$ and $C$, we can find $B$ by using $xor$ between $A$ and $C$.
After that, we will verify the first condition. If $X + Y > n$, then we can’t take a prefix of length $X$ . Otherwise, taking a prefix with length $X$ and a suffix of length $Y$ is a possible solution.
For such candidate solutions, we will find the summation of the first $X$ values and the last $Y$ values by precomputing the prefix sum of the array, followed by storing the maximum sum.
The prefix sum will be the summation of the range $[1, X]$ and the suffix sum will be the summation of the range $[n-Y+1, N]$, which can be calculated in a constant time with the above arrays.
The complexity of the solution is $O(n)$, which is the time needed to fill the prefix sum arrays and brute-forcing the value of $X$.