A Classical Problem?
Difference between en1 and en2, changed 47 character(s)
You are given a permutation of $n$. Build an undirected graph of $n$ nodes. There is an edge $(i,j)$ if and only if $i<j$ and $p_i < p_j$. Please find the maximum matching of the graph.↵
↵
I don't know how to do it in $O(n \log n)$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English JianfengZhu 2023-05-19 11:51:55 47 Tiny change: 'the graph.' -> 'the graph.\n\nI don't know how to do it in $O(n \log n)$.'
en1 English JianfengZhu 2023-05-19 11:51:17 205 Initial revision (published)