# Three Subarrays DSA Interview Problem Three Subarrays DSA Interview Problem

In Three Subarrays DSA Interview Problem, you are given an array A of n integers. You have to pick 3 subarrays from the arrays l1, l2, and l3. Let’s together first see the original problem statement and then try to solve the problem

## Three Subarrays DSA Interview Problem Statement

You are given an array

$A$$A$ of

$n$$n$ integers. You will have to pick

$3$$3$ subarrays from the array

${l}_{1}$$l_1$,

${l}_{2}$$l_2$, and

${l}_{3}$$l_3$. The subarray

${l}_{1}$$l_1$ must be a prefix and

${l}_{3}$$l_3$ must be suffix. Minimum length of the all the subarrays must be

$1$$1$. An Element of the array

$A$$A$ cannot be present in more than

$1$$1$ of these subarrays.

Find the maximum sum of all the elements in each of these

$3$$3$ subarrays.

Input

The first line of input contains an integer

$t\phantom{\rule{2pt}{0ex}}\left(1\le t\le {10}^{4}\right)$$t \hspace{2pt} (1 \le t \le 10^4)$ — the number of testcases. The description of

$t$$t$ testcases follows.

The first line of each testcase contains an integer

$n\phantom{\rule{2pt}{0ex}}\left(3\le n\le {10}^{5}\right)$$n \hspace{2pt} (3 \le n \le 10^5)$ — the number of elements in the array

$A$$A$.

The second line of each testcase contains

$n$$n$ space separated integers

${a}_{0},{a}_{1},...{a}_{n}$$a_0, a_1, ... a_n$

$\left(-{10}^{9}\le {a}_{i}\le {10}^{9}\right)$$(-10^9 \le a_i \le 10^9)$ — the elements of array

$A$$A$.

It is guaranteed that the sum of

$n$$n$ over all testcases does not exceed

${10}^{5}.$$10^5.$

Output

For each testcase, print a single integer — the maximum sum of all elements in the three subarrays.

Example
Input
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

Output
5
2
23

Note

In sample testcase 1, we can choose the three subarrays as

$\left\{\left[2\right],\left[-1\right],\left[4\right]\right\}$$\{, [-1], \}$. The sum is hence

$5$$5$.

In sample testcase 2, we can choose the three subarrays as

$\left\{\left[-6\right],\left[1\right],\left[5,2\right]\right\}$$\{ [-6], , [5,2]\}$. The sum is hence

$2$$2$.

## Three Subarrays DSA Interview Problem Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
vector<ll> v;
ll sum=0;
for(ll i=0;i<n;i++)
{
ll a;
cin>>a;
v.push_back(a);
sum+=a;
}
vector<ll> left(n,0);
vector<ll> right(n,0);
left=0;
// minimum sum subarray including ith index
for(ll i=1;i<n-1;i++)
{
left[i]=min(v[i]+left[i-1],v[i]);
}
//minimum sum subarray from ith to n not including ith index
right[n-1]=0;
for(ll i=n-2;i>0;i--)
{
right[i]=min(right[i+1]+v[i],v[i]);
}
// minimum sum subarray not including ith index [0..i-1]
// minimum sum subarray not including ith index [i+1...n]
vector<ll> d1(n,0);
vector<ll> d2(n,0);
d1=0;
for(ll i=1;i<n-1;i++)
{
d1[i]=min(left[i-1],d1[i-1]);
}
d2[n-1]=0;
for(ll i=n-2;i>0;i--)
{
d2[i]=min(right[i+1],d2[i+1]);
}
ll ans=LONG_MIN;
for(ll i=0;i<n;i++)
{
ans=max(ans,sum-d2[i]-d1[i]);
}
cout<<ans<<endl;
}
return 0;
}