@above
Correction..
i can be <= R... hence, which can be found as part of traversal..
Another addition:
I have explained the concept using A[j] to be max.. In case A[j] is
min, then we will take a similar approach keeping in mind that R will
be closest but in terms of finding the max element..
On 31 Dec, 20:08, Lucifer <sourabhd2...@gmail.com> wrote:
> 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 <topcode...@gmail.com> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
