Maximum Glide Path

Moderate

0/80

0 upvote

Asked in company

Problem statement

There are n mountains in a row, with their heights given by an array h. You are planning a hang gliding route and want to find the longest possible trip, measured by the number of mountains visited.

A trip consists of a sequence of glides. You can start your trip at any mountain. From a mountain a at index i, you can glide to a mountain b at index j if and only if:

Mountain a is strictly taller than mountain b (h[i] > h[j]).

All mountains physically located between a and b are also strictly shorter than mountain a.

A route can change direction. For example, a valid route could be starting at mountain i, gliding left to mountain j, and then gliding left again to mountain k. Another valid route could start at i, glide right to j, and then glide right again. A third valid route could involve a path that goes left from a peak and a path that goes right from the same peak.

Your task is to find the maximum number of distinct mountains that can be visited in a single continuous route.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer n, the number of mountains.

The second line contains n space-separated integers, h_1, h_2, ..., h_n, representing the heights of the mountains.

Output Format:

Print a single integer representing the maximum number of mountains that can be visited.

Note:

This problem can be modeled as finding the longest path in a Directed Acyclic Graph (DAG), where mountains are nodes and valid glides are edges.

Sample Input 1:

10
20 15 17 35 25 40 12 19 13 12

Sample Output 1:

Explanation for Sample 1:

The logic involves two passes. Let L[i] be the longest path ending at i from the left, and R[i] be the longest path ending at i from the right.
  The mountain with height 40 (index 5) is a peak. L[5] = 1.
  A path starting at 40 and going right is 40 -> 25 -> .... The R array value for index 5 will be calculated by a right-to-left pass. R[5] represents the longest path starting from the right and ending at 40. Example: 12 -> 13 -> 19 -> 40. The length is 4.
  The final answer is max(L[i] + R[i] - 1). For i=5, this is L[5] + R[5] - 1 = 1 + 4 - 1 = 4.
  Let's check the peak at 35 (index 3). L[3]=1. The path 12->13->17->...->35 from the right gives R[3]=5. L[3]+R[3]-1 = 1+5-1=5. This is the maximum.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= n <= 2 * 10^5
1 <= h_i <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Maximum Glide Path

Console