 # DECOSUM - Editorial

Author: Ritesh Gupta
Editorialist: Ritesh Gupta

Simple-Easy

# PROBLEM:

You are given a sequence A_1, A_2, \ldots, A_N. You have to find the length of a minimum positive-sum subarray. If there is more than one answer then print the largest length possible or if no subarray satisfies the given property then print “-1”.

# Constraints:

• 1 \le T \le 5
• 1 \le N \le 10^5
• 0 \le A_i \le 10^6 for each valid i

# EXPLANATION:

If the sum of all the elements is zero then the answer would be “-1” else answer always exists. As we need to find the minimum positive-sum possible so we should select the subarray which contains only one occurrence of the minimum positive element of the sequence and rest are zeros.

Let’s denote l_i for each valid i, as the size of zero-subarray which ends at index i and r_i for each valid i, as the size of zero-subarray which starts at index i.

Also assume that l_0 = r_n = 0.

If there are m occurences of smallest element of the sequence and represents by sequence k_1, k_2, ..., k_m such that A_{k_i} has smallest element then answer to the problem is:
maximum of l_{k_{i-1}} + r_{k_{i+1}} + 1 for each valid i.

# SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
int t;
cin >> t;

``````while(t--)
{
int n;
cin >> n;

vector <int> v;
int mx = 0;
int mi = 1e9;

for(int i=0;i<n;i++)
{
int x;
cin >> x;

mx = max(mx,x);

if(x > 0)
mi = min(mi,x);

v.push_back(x);
}

if(mx == 0)
cout << -1 << endl;
else
{
int ans = 1;

for(int i=0;i<n;i++)
{
if(v[i] == mi)
{
int cnt = 1;
int j = i-1;

while((j >= 0) && (v[j] == 0))
cnt++, j--;

j = i+1;

while((j < n) && (v[j] == 0))
cnt++, j++;

ans = max(ans,cnt);
}
}

cout << ans << endl;
}
}
``````

}

Tester's Solution

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;

int main()
{
int t,n;
cin>>t;

``````while(t--)
{
cin>>n;
vector<int> v(n);

int z=0,lo=1e9+7;

for(int i=0;i<n;i++)
{
cin>>v[i];

if(v[i])
lo=min(lo,v[i]);
else
z++;
}

if(z==n)
cout<<-1<<endl;
else if(!z)
cout<<1<<endl;
else
{
vector<int> pre(n),suf(n);

if(!v)
pre++;

for(int i=1;i<n;i++)
{
if(!v[i])
pre[i]=pre[i-1]+1;
else
pre[i]=0;
}

if(!v[n-1])
suf[n-1]++;

for(int i=n-2;i>=0;i--)
{
if(!v[i])
suf[i]=suf[i+1]+1;
else
pre[i]=0;
}

int ans=0;

for(int i=0;i<n;i++)
{
if(v[i]==lo)
{
int tmp=0;
if(i)
tmp+=pre[i-1];
if(i!=n-1)
tmp+=suf[i+1];
ans=max(ans,1+tmp);
}
}

cout<<ans<<endl;
}
}
``````

}

1 Like

thanks this editorial is really helpfull 