Longest Subsequence

The problem of finding the longest monotonically decreasing subsequence has an O(n log n) solution. My soln is .

Absolutely fascinating that a sequence can be represented as a permutation graph, which means that the problem of finding the longest subsequence morphs into the problem of finding the largest clique!

Thus, essentially, the question which I was trying to solve – prove that a sequence from 1…101, will contain a increasing or decreasing sub-seq of length 10, morphs into a problem of proving that the ramsey number is 10.

Advertisement