Arunachalam wrote: > Had anyone tried coding this solutions. I have got wrong answer for the > implementation. Might be a coding flaw too. > > If anyone is able to successfully crack it , please share your solution.
Another worst-case O(n log n) solution: 1. (O(n)) Set values of sum[] where sum[1] = hv[1] and sum[i] = hv[i] + sum[i - 1] for i > 1. Use sum[] later to calculate the sum over any range of days in O(1) time. (hv[i] is happiness value for day i .) 2. (O(n log n) Initialize an array x[1..n] so that x[i] = i . Sort x[] on the major key of hv[x[i]] and the minor key of x[i]. (That is, make x[] and array of day numbers, sorted by ascending happiness values, with days with the same happiness value sub-sorted ascendingly by day number. 3. (O(n log n)) let first = 1, last = n, best = sum[n] * hv[x[1]], start_hv = 1, try = n; for i = 2 to n { if (hv[x[i]] > hv[x[start_hv]]) { insert elements of x[] in the range from start_hv to i - 1 into a balanced search tree ordered by the day value; start_hv = i, try = 0; } day = x[i]; if (day > try and hv[day] > hv[day - 1]) { // See if best interval starting with day is best so far. let try = least node in balanced search tree > day; if (no node greater than day in b.s.t.) try = n; else try = try - 1; b = hv[day] * (sum[try] - sum[day - 1]) if (b > best) best = b, first = day, last = try; } The result is the interval of days from 'first' to 'last' --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---