PROBLEM LINK:
Author: Tushar Sharma
Tester: Gaurav,Pratyaksh
Editorialist: Tushar Sharma
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Two-Pointers
PROBLEM:
You are given N integers and an initial value S. You have to find out the longest contiguous subsequence, where while adding each of the values to S, it never becomes less than 0
EXPLANATION:
We can easily observe that a simple two pointer approach is required to solve this problem.
Suppose we take two pointers as start and end, and initially we set both of them to 0, and set initial value of sum variable as S. Then, we slide the end pointer until the value of sum is positive, and keep track of the maximum length of subsequence till current position. If value of sum becomes negative, the we slide the start pointer until the value again becomes positive.
When our end pointer reaches the last integer, then we terminate the loop, and if the length of the subsequence is greater than 0, we print the left and right pointers, otherwise we print -1
SOLUTIONS:
Editorialist's, Setter's Solution
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
ll size, sum, maxLen=0, start=0, end=0, l=-1 , r=-1;
cin>>size>>sum;
vector v(size);
for(int i=0;i<size;i++)
cin>>v[i];
while(end<size && start<size){
if(sum+v[end]>=0){
if(maxLen<end-start+1){
maxLen=end-start+1;
l=start+1;
r=end+1;
}
sum+=v[end];
end++;
}else{
if(start<end)
sum-=v[start++];
else {
start++;
end++;
}
}
}
if(maxLen==0)
cout<<"-1\n";
else cout<<l<<" "<<r<<"\n";
}
int main()
{
int tcases=1;
cin>>tcases;
while(tcases)
{
solve();
--tcases;
}
return 0;
}
First Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// your code goes here
int test;
cin>>test;
while(test--){
long long n,s;
cin>>n>>s;
vector<long long>a(n);
for(int i=0;i<n;i++)
cin>>a[i];
long long i=0,j=0,x,y;
long long sum=0,ans=-1;
while(i<n){
sum+=a[i];
if(sum+s>=0){
if(i-j>ans){
ans=i-j;
x=j; y=i;
}
}
else{
while((j<=i)&&((sum+s)<0)){
sum-=a[j];
j++;
}
}
i++;
}
if(ans>-1)
cout<<x+1<<' '<<y+1<<endl;
else
cout<<"-1\n";
}
return 0;
}
Second Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// your code goes here
int test;
cin>>test;
while(test--){
long long n,s;
cin>>n>>s;
vector<long long>a(n);
for(int i=0;i<n;i++)
cin>>a[i];
long long i=0,j=0,x,y;
long long sum=0,ans=-1;
while(i<n){
sum+=a[i];
if(sum+s>=0){
if(i-j>ans){
ans=i-j;
x=j; y=i;
}
}
else{
while(j<=i&&sum+s<0){
sum-=a[j];
j++;
}
}
i++;
}
if(ans>-1)
cout<<x+1<<' '<<y+1<<endl;
else
cout<<"-1\n";
}
return 0;
}