You are viewing a single comment's thread. Return to all comments →
here is an explanation:
We basically have to find sequences of numbers which are always increasing and those which are decreasing. initialise a count array of length n with all 1. then whenever u see an increasing pattern, set the bigger number count = smaller number count + 1 while traversing the array forward.
then traverse the array backwards and check for the same increasing pattern (which would be decreasing since we are traversing backward). but only do the bigger number count = smaller number count + 1 when (bigger number count <= smaller number count). this is because we might already have set the value to something bigger before while traversing forward.
here is an example,
array : 2 4 5 6 7 8 9 5 4
count : 1 2 3 4 5 6 7 2 1
count array can look like a mountain. increase then decrease
the peak of the mountain (9 here) is determined by which slope is longer, left or right. that is why u have that check while traversing backards.
try manually doing this and u will see why:
array : 2 9 8 6 4 3 2 1
count : 1 7 6 5 4 3 2 1