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 [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
-~----------~----~----~----~------~----~------~--~---
