The Ascending Mountain Path
Priya is hiking in the Himalayas and wants to find the longest path on a map represented as a sequence of mountain peaks. Each peak has a specific altitude. A path can only go from peak i to peak j if j > i and the altitude of peak j is strictly greater than the altitude of peak i. Priya wants to find the maximum number of peaks she can visit in a single valid path.
Given the altitudes of n peaks in order, find the length of the longest ascending mountain path.
Input
The first line contains an integer n, the number of peaks. The second line contains n space-separated integers representing the altitudes of the peaks, a_1, a_2, ..., a_n.
Output
Print a single integer: the length of the longest ascending mountain path.
Constraints
1 <= n <= 200000 1 <= a_i <= 10^9
Example 1
5 1 3 2 4 5
4
The longest path is 1 -> 3 -> 4 -> 5, with length 4.
Example 2
7 10 9 8 7 6 5 4
1
All paths have length 1 as the sequence is strictly decreasing.
Hints
Similar problems
- Longest Non-Decreasing SubsequenceHard
- Maximum Sum of Non-Overlapping IntervalsHard
- Maximum Sum of Non-Adjacent ElementsHard
- Longest Increasing Subsequence with Stack ConstraintHard
- The Harmonious SequenceHard
- Maximum Sum Subarray with Length ConstraintHard
More in: Dynamic Programming problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 3 2 4 5
7 10 9 8 7 6 5 4