Superhero :
Difficulty Level : Hard
Submissions : 291
Asked In :
Marks :20
: 8 | : 1
You are given two 0-indexed integer arrays $$$A$$$ and $$$B$$$, containing $$$n$$$ integers each.
You can choose two integers $$$l$$$ and $$$r$$$ where $$$0 \le l \le r < n$$$ and swap the subarray $$$A[l...r]$$$ with the subarray $$$B[l...r]$$$.
For example, if $$$A = [1,2,3,4,5]$$$ and $$$B = [11,12,13,14,15]$$$ and you choose $$$l = 1$$$ and $$$r = 2$$$, $$$A$$$ becomes $$$[1,12,13,4,5]$$$ and $$$B$$$ becomes $$$[11,2,3,14,15]$$$.
You may choose to apply the mentioned operation once or not do anything.
The score of the arrays is the maximum of $$$sum(A)$$$ and $$$sum(B)$$$, where $$$sum(arr)$$$ is the sum of all the elements in the array $$$arr$$$.
Your task is to find the maximum possible score.
Note: A subarray is a contiguous sequence of elements within an array. $$$arr[l...r]$$$ denotes the subarray that contains the elements of arr between indices $$$l$$$ and $$$r$$$ (inclusive).
The first line of input contains an integer $$$t \hspace{2pt} (1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains an integer $$$n \hspace{2pt} (1 \le n \le 10^5)$$$ — the number of elements in the arrays $$$A$$$ and $$$B$$$.
The second line of each testcase contains $$$n$$$ space separated integers $$$a_0, a_1, ... a_n$$$ $$$(0 \le a_i \le 10^9)$$$ — the elements of array $$$A$$$.
The third line of each testcase contains $$$n$$$ space separated integers $$$b_0, b_1, ... b_n$$$ $$$(0 \le b_i \le 10^9)$$$ — the elements of array $$$B$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5.$$$
For each testcase, print a single integer — the maximum possible score in a new line.
3360 60 6010 90 10520 40 20 70 3050 20 50 40 2037 11 131 1 1
210 220 31
In sample testcase 1, one of the optimal ways is to choose $$$l = 1$$$ and $$$r = 1$$$. Then, $$$A = [60,90,60]$$$ and $$$B = [10,60,10]$$$. The score is $$$max(sum(A),sum(B)) = max(210,80) = 210$$$.
In sample testcase 2, one of the optimal ways is to choose $$$l = 3$$$ and $$$r = 4$$$. Then, $$$A = [20,40,20,40,20]$$$ and $$$B = [50,20,50,70,30]$$$. The score is $$$max(sum(A),sum(B)) = max(140,220) = 220$$$.
In sample testcase 3, we choose not to swap any subarray. The score is $$$max(sum(A),sum(B)) = max(31,3) = 31$$$.
