Longest Increasing Subsequence on a Permutation
HardPractice library · +30 XPrecursiondynamic programminggreedy
Given a permutation of the integers from 1 to N, find the length of the longest increasing subsequence.
Input
The first line contains an integer N. The second line contains N distinct integers, representing a permutation of 1 to N.
Output
Print a single integer, the length of the longest increasing subsequence.
Constraints
1 <= N <= 200000
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 3 1 4 2 5
Output
3
The LIS is {3, 4, 5} or {1, 2, 5}, length is 3.
Example 2
Input
7 1 2 3 4 5 6 7
Output
7
The LIS is {1, 2, 3, 4, 5, 6, 7}, length is 7.
Hints
Similar problems
- Longest Increasing Subsequence with Stack ConstraintHard
- Maximum Sum of Non-Overlapping IntervalsHard
- Maximum Sum of Consecutive SubsegmentsMedium
- Longest Zigzag SubsequenceMedium
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Lexicographically Smallest PathMedium
More topics: Greedy problems, Dynamic Programming problems, Recursion problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 3 1 4 2 5
Example 2 input
7 1 2 3 4 5 6 7