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.