miss

 miss(p) -- maximum increasing subsequence
 Viewing the permutation p as a sequence (return from array(p)) find a
 longest increasing subsequence. May also be called with two arguments:
 miss(p,'up') -- find longest increasing subsequence
 miss(p,'down') -- find longest decreasing subsequence

0001 function s = miss(p,dir)
0002 % miss(p) -- maximum increasing subsequence
0003 % Viewing the permutation p as a sequence (return from array(p)) find a
0004 % longest increasing subsequence. May also be called with two arguments:
0005 % miss(p,'up') -- find longest increasing subsequence
0006 % miss(p,'down') -- find longest decreasing subsequence
0007 
0008 if nargin < 2
0009     dir = 'up';
0010 end
0011 
0012 switch(lower(dir))
0013     case 'up'
0014         a = array(p);
0015         s = miss_array(a);
0016     case 'dn'
0017         a = array(p);
0018         a = fliplr(a);
0019         s = miss_array(a);
0020         s = fliplr(s);
0021     otherwise
0022         error('Second argument should be ''up'' or ''down''.');
0023 end
0024 end
0025 
0026 
0027 
0028 
0029 function ss = miss_array(a)
0030 n = length(a);
0031 up = zeros(1,n);
0032 up(n) = 1;
0033 
0034 % create an array up whose i'th element gives the length of the longest
0035 % increasing subsequence starting at position i.
0036 for i=(n-1):-1:1
0037     up(i) = 1;
0038     for j=(i+1):n
0039         if (a(i) < a(j))
0040             if (up(i) <= up(j))
0041                 up(i) = up(j)+1;
0042             end
0043         end
0044     end            
0045 end
0046 
0047 % now use the up array to find longest subseq
0048 maxup = max(up);
0049 si = find(up==maxup,1,'first');
0050 for k=(maxup-1):-1:1
0051     tail = up(si(end)+1:end);
0052     i = find(tail==k,1,'first');
0053     si = [si, si(end)+i];
0054 end
0055     
0056 ss = a(si);
0057    
0058 end
0059