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$ 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\phantom{\rule{2pt}{0ex}}(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\phantom{\rule{2pt}{0ex}}(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$.

## 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]=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]=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;
}
```

## Leave a Reply