O(N^2) approach..
-----------------------------------
Say the current start index is i..
Then starting from i keep track of the min and max element and ensure
that the diff of max and min is <=K.
Say the diff exceeds at index j, then the current continuous subarray
size would be (j - i) and we will compare it against the previously
recorded maximum value.
Code:
-------------
Say the given array of integers is represented by A[N] and the diff is
represented by K.
int currMax = 0;
int strtInd = -1;
int endInd = -1;
for( int i =0; i < N; ++i)
{
int j = i;
int min = A[i] , min = A[i];
while ( ++j < N )
{
if ( A[j] < min)
min = A[j];
else if (A[j] > max)
max = A[j];
else
continue;
if (max - min > k)
break;
}
if ( (j - i) > currMax)
{
currMax = j - i;
strtInd = i;
endInd = j-1;
}
// Break if true,
// as we know that it is the max size
// that we can get..
if ( j==N)
break;
}
printf(" Max subarray size :%d, Start Index : %d, End Index : %d",
currMax, strtInd, endInd);
-----------------------------------------------------------------
An optimized O(N^2) approach to reduce the no. of computations :-
Once the inner loop breaks, instead of starting from the next start
index i.e 'i+1' we can optimize on it as follows:
Say, the index 'j' at which the inner loop breaks was due to a new max
value i.e. A[j].
Now, to readjust the start index for the next iteration we will
traverse elements from index 'i+1' to 'j-1' to get the closest value
to (A[j] - K), which is also >= (A[j] - K).
Say, the index of the closest value found is R, then for the next
iteration the start values will be initialized as follows..
i = R;
j = current value of j + 1 , as R to j already satisfies the
'difference of K' condition.
min = A[R];
max = A[j];
------------------------------------------------------
Based on above 2nd approach i could think of a NlogN algorithm which i
will post next..
--------------------------------------------------------
On 27 Dec, 22:00, top coder <[email protected]> wrote:
> Find the longest continuous subsequence of numbers in an unsorted
> array such that difference between any two nos. in that sequence
> should not be more than K.
> For example:
> 2,1,8,12, 10,15, 13, 25 and k=7
>
> 8,12,10,15,13 is the sequence (15-8=7)
--
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.
