Three Subarrays DSA Interview Problem

Three Subarrays DSA Interview Problem

by

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

l1,

l2, and

l3. The subarray

l1 must be a prefix and

l3 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.

Input

The first line of input contains an integer

t(1≤t≤104) — the number of testcases. The description of

t testcases follows.

The first line of each testcase contains an integer

n(3≤n≤105) — the number of elements in the array

A.

The second line of each testcase contains

n space separated integers

a0,a1,...an

(−109≤ai≤109) — the elements of array

A.

It is guaranteed that the sum of

n over all testcases does not exceed

105.

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

{[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 Comment