HNY 2012(IST) in between to all members and happy coding for 2012 may all your compilation produce ZERO errors
On Sun, Jan 1, 2012 at 12:01 AM, Lucifer <[email protected]> wrote: > @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 <[email protected]> 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 <[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. > > -- 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.
