Asymptotic bound on number of Longest Increasing Subsequences.

Правка en1, от vishaaaal, 2021-07-19 20:24:20

Consider an array of length $$$n$$$ and we want to count the number of increasing subsequences such that their length is the maximum among all different increasing subsequences in this array(obviously the count can be more than 1). What will be the asymptotic bound on our answer?
In other words, what is the order of our answer? Is it $$$O(n)$$$ or $$$O(nlogn)$$$ or $$$O(n^2)$$$?
Consider all the elements in the array distinct. Can we also expand the same solution for arrays with multiple occurrences of elements?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский vishaaaal 2021-07-19 20:24:20 573 Initial revision (published)