PROBLEM LINK:
Author: Sibasish Ghosh
Testers: Pritish Nayak, Niket Agarwal
Editorialist: Sibasish Ghosh
DIFFICULTY:
Simple
PREREQUISITES:
Dynamic Programming, Greedy
PROBLEM:
Given an array A consisting of N integers, find the length of the maximum subarray such that the absolute difference between adjacent elements in the subarray is at most K (Note that the minimum length has to be 2 for the condition to be applicable).
EXPLANATION:
This has a pretty straightforward approach. Let’s start with i=0. Keep incrementing i until the condition |A_i-A_{i+1}|\leq K is satisfied. Suppose we are at index j now. The subarray A[i...j] is a valid subarray. Can we get a better result if we start at an index between i and j? NO (Why?). So, next, we start from index j+1 and find out the length of the next valid subarray. We do this until we reach the end of the array. Finally, the answer would be the maximum of the lengths of all the valid subarrays.
Refer to the solutions below if you face any problem.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input6.txt","r",stdin);
// freopen("output6.txt","w",stdout);
ll t=1;
cin>>t;
while(t--)
{
ll n,k,i,ans=0;
cin>>n>>k;
ll a[n+10],dp[n+10];
for(i=1;i<=n;i++)
{
cin>>a[i];
dp[i]=1;
}
for(i=2;i<=n;i++)
{
if(abs(a[i-1]-a[i]) <= k)
dp[i]=dp[i-1]+1;
}
for(i=1;i<=n;i++)
ans=max(ans,dp[i]);
if(ans <= 1)
cout<<"-1\n";
else cout<<ans<<"\n";
}
return 0;
}
Tester's Solution (Pritish)
/** ���翻訳��������������人�������貴������������ **/
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repr(i,x,y) for(int i=x;i>=y;i--)
#define int long long
#define pb push_back
#define ff first
#define ss second
#define sz(x) ((int)x.size())
#define all(x) begin(x), end(x)
using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<pair<int,int>>;
constexpr int mod = 1000000007;
constexpr int N = 2e8 + 5;
constexpr int inf = 1e18 , eps = 1e-6;
int sumn=0;
void Onigiri()
{
int n,k;
cin>>n>>k;
sumn+=n;
assert(sumn<=1000000);
assert(n>=2&&n<=100000);
assert(k>=1&&k<=1000000000);
int a[n];
rep(i,0,n){
cin>>a[i];
assert(a[i]>=1&&a[i]<=1000000000);
}
int ans=-1,cnt=1;
rep(i,1,n)
if(abs(a[i]-a[i-1])<=k){cnt++;}
else {ans=max(ans,cnt);cnt=1;}
ans=max(ans,cnt);
if(ans<=1)cout<<-1;
else cout<<ans;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifdef Zoro
freopen("/home/pritish/Competitive/in", "r", stdin);
freopen("/home/pritish/Competitive/out", "w", stdout);
#endif
int t=1;
cin>>t;
assert(t>=1&&t<=100000);
while(t--)
{Onigiri();cout<<"\n";}
cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}
Tester's Solution (Niket)
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
public static void process()throws IOException
{
int n=ni();
int k=ni();
int[]A=nai(n);
int c=0;
int ans=0;
for(int i=0;i<n-1;i++)
{
if(Math.abs(A[i]-A[i+1])<=k)
c++;
else
{
ans=Math.max(ans,c);
c=0;
}
}
ans=Math.max(ans,c);
if(ans==0)
ans--;
else ans++;
pn(ans);
}
static AnotherReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
boolean oj = true;
if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
int t=1;
t=ni();
while(t-->0) {process();}
out.flush();out.close();
}
static long mod=(long)1e9+7l;
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class AnotherReader{BufferedReader br; StringTokenizer st;
AnotherReader()throws FileNotFoundException{
br=new BufferedReader(new InputStreamReader(System.in));}
AnotherReader(int a)throws FileNotFoundException{
br = new BufferedReader(new FileReader("input.txt"));}
String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
st = new StringTokenizer(br.readLine());}
catch (IOException e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
Feel free to write your approach in the comments 