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");

}

### Like this:

Like Loading...

*Related*

"One problem can be solved in thousands of ways, but there will be only one best solution"this is so not true