Three Subarrays :
Difficulty Level : Medium
Submissions : 1080
Asked In :
Marks :15
: 32 | : 0
You are given an array $$$A$$$ of $$$n$$$ integers. You will have to pick $$$3$$$ subarrays from the array $$$l_1$$$, $$$l_2$$$, and $$$l_3$$$. The subarray $$$l_1$$$ must be a prefix and $$$l_3$$$ must be suffix. Minimum length of the all the subarrays must be $$$1$$$. An Element of the array $$$A$$$ cannot be present in more than $$$1$$$ of these subarrays.
Find the maximum sum of all the elements in each of these $$$3$$$ subarrays.
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} (3 \le n \le 10^5)$$$ — the number of elements in the array $$$A$$$.
The second line of each testcase contains $$$n$$$ space separated integers $$$a_0, a_1, ... a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — the elements of array $$$A$$$.
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 sum of all elements in the three subarrays.
3 4 2 -3 -1 4 6 -6 -2 1 -4 5 2 14 1 2 3 -10 3 4 5 -100 4 5 3 -10 2 1
5 2 23
In sample testcase 1, we can choose the three subarrays as $$$\{[2], [-1], [4]\}$$$. The sum is hence $$$5$$$.
In sample testcase 2, we can choose the three subarrays as $$$\{ [-6], [1], [5,2]\}$$$. The sum is hence $$$2$$$.
