Longest Non-Decreasing Subsequence
Given a sequence of N integers, find the length of the longest subsequence such that all elements in the subsequence are in non-decreasing order. A subsequence is obtained by deleting zero or more elements from the original sequence. For example, in the sequence [1, 3, 2, 4, 5], [1, 2, 4, 5] is a non-decreasing subsequence, and its length is 4. This is the longest such subsequence.
Input
The first line contains an integer N. The second line contains N integers representing the sequence.
Output
Print a single integer, the length of the longest non-decreasing subsequence.
Constraints
1 <= N <= 200000 Each integer in the sequence is between -10^9 and 10^9.
Example 1
5 1 3 2 4 5
4
The longest non-decreasing subsequence is [1, 2, 4, 5] with length 4.
Example 2
7 3 1 4 1 5 9 2
4
The longest non-decreasing subsequence is [1, 1, 5, 9] or [1, 1, 2] or [3, 4, 5, 9] etc. The maximum length is 4.
Hints
# 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 3 1 4 1 5 9 2