@ Optimization ... O(N).. single run O(n^2)
Basically in a single run we can calculate the maximum value using
praveen's logic..
Say, A[N] is the array of integers..
And X[N+1] stores the intermediate values for maximum size subarray...
int max = 0;
int strtind = -1;
int endind = -1;
for(int i =0; i<= N; ++i)
X[i] = 0;
for (int i = 0; i < N; ++i)
for (j = N; j > 0; --j)
{
X[j] = ( abs(A[i] - A[j]) > K ) ? 0 : 1+ min( X[j],
X[j-1] ) ;
if ( A[j] > max)
{
max = A[j];
strtind = i - max + 1;
endind = j - 1;
}
}
On Jan 3, 12:57 am, Lucifer <[email protected]> wrote:
> @above..
> I m sorry,
> A would be 1 2 3 4 5 ..
>
> On Jan 3, 12:03 am, atul anand <[email protected]> wrote:
>
>
>
>
>
>
>
> > @praveen : i guess we can optimize the space to O(n);
>
> > if diff b/w two number is <=K then A[i]=A[i-1]+1;
>
> > if condition fails temp_maxLen=A[i-1];
> > if(temp_maxlen > maxLen)
> > {
> > maxLen=temp_maxlen;
>
> > }
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
