maximum length subarray such that maximum difference is less than k


Problem
#include <stdio.h>


typedef struct
{
int start;
int end;
}Ret;


Ret maxsubarr(int a[], int n, int k)
{
Ret r = {0, 0};


int start = 0, end = 0;
int max = 0, min = 0;

int i;

int d1, d2;

int numcomp = 0; //number of comparisons to find the complexity

for(i = 1; i < n; ++i) //loop through all the elements
{
d1 = a[max] - a[i];
d2 = a[min] - a[i];

numcomp += 2;

if(abs(d1) <= k && abs(d2) <= k)//a[max] - k <= a[i] <= a[min] + k
{
end = i;
if(a[max] < a[i])
{
max = i;
}
else if(a[min] > a[i])
{
min = i;
}

numcomp += 2;
}

else
{
if((end - start) > (r.end - r.start)) //end of turn
{
r.start = start;
r.end = end;
}

if(d1 < -k || d2 > k) //a[i] > a[max] + k or a[i] < a[min] - k
{
//out of bounds, reset
max = min = end = start = i;
}
else //a[min] - k <= a[i] <= a[max] + k
{
int j, x;
end = i;

if(d1 >= -k) //a[i] <= a[max] + k
{
start = min + 1;

max = i;

//eliminate elements < x and find min
x = a[max] - k;

for(j = start + 1; j < end; j++)
{
numcomp++;
if(a[j] < x)
start = j + 1;
}

min = start;
for(j = start + 1; j < end; j++)
{
numcomp++;
if(a[min] > a[j])
min = j;
}
}
else //a[i] >= a[min] - k
{
start = max + 1;

min = i;

x = a[min] + k;

//eliminate elements > x and find max

for(j = start + 1; j < end; j++)
{
numcomp++;
if(a[j] > x)
start = j + 1;
}

max = start;
for(j = start + 1; j < end; j++)
{
numcomp++;
if(a[max] < a[j])
max = j;
}
}

}

}

}

if((end - start) > (r.end - r.start))
{
r.start = start;
r.end = end;
}

printf("numcomp %d, numele %d\n", numcomp, n);
return r;

}

int main()
{
int a[] = {2,1,8,12,10,15,12,25};

Ret r = maxsubarr(a,sizeof(a)/sizeof(int), 7);

int i;

for(i = r.start; i <= r.end; ++i)
printf("%d ", a[i]);

printf("\n");
}
Advertisements

One thought on “maximum length subarray such that maximum difference is less than k

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s