Given a string S = {a1, a2, a3, ..., an}, the longest increasing subsequence (LIS) problem is to find a subsequence of the given string such that the subsequence is increasing and its length is maximal. In a previous result, to find the longest increasing subsequences of each sliding window with a fixed size w of a given string with length n can be solved in O(w log log n+OUTPUT) time, where O(w log log n+ w^2) time is taken for preprocessing and OUTPUT is the sum of all output lengths. In this thesis, we solve the problem for finding the longest increasing subsequence of every substring of S. With the straightforward implementation of the previous result, the time required for the preprocessing would be O(n^3). We modify the data structure used in the algorithm, hence the required preprocessing time is improved to O(n^2). The time required for the report stage is linear to the size of the output. In other words, our algorithm can find the LIS of every substring in O(n^2+OUTPUT) time. If the LIS's of all substrings are desired to be reported, since there are O(n^2) substrings totally in a given string with length n, our algorithm is optimal.

The distribution theory of runs and patterns has a long and rich history. In this dissertation we study the distribution of some run-related statistics in sequences and random permutations of arbitrary multi-sets. Using the finite Markov chain imbedding technique (FMCI), which was proposed by Fu and Koutras (1994), we proposed an alternative method to calculate the exact distribution of the total number of adjacent increasing and adjacent consecutive increasing subsequences in sequences. Fu and Hsieh (2015) obtained the exact distribution of the length of the longest increasing subsequence in random permutations. To the best of our knowledge, little or no work has been done on the exact distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets. Here we obtained the exact distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets. We also obtain the the exact distribution of the length of the longest increasing subsequence for the set of all permutations of length N generated from {1,2,...,n}. / February 2016