## Longest increasing sub-sequence

According to this blog, "The

**longest increasing sub-sequence**problem is to find a sub-sequence of a given sequence in which the sub-sequence elements are in sorted order, lowest to highest, and in which the sub-sequence is as long as possible". As an example, for 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 they give one longest increasing sub-sequence as 0, 2, 6, 9, 13, 15.### Python

'''Find a longest increasing subsequence http://basicalgos.blogspot.com/2012/03/37-longest-increasing-sequence-lis.html ''' import functools def ics (s): #s is s sequence """Find the set of increasing subsequences of s. """ if len (s) == 1 : return [s] #s itself is an ics of length 1 #This is the key point. ts = ics (s[1:]) #ts are the ics values of s - it's first element #Extend ts with any new subsequences that can be formed by #prepending s[0] to t for t in ts. def f (acc, t) : if s[0] < t[0]: nt = [s[0]]+t return acc + [nt] else: return acc res = functools.reduce (f, ts, ts) + [[s[0]]] return res #s, the input sequence. s=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] #Print all longest increasing subsequences of s. res = ics (s) #Find every ics of s lens=list (map (lambda x : len (x), res)) #Now their lengths lismax= \ functools.reduce (\ lambda acc, y: max (acc, y), lens, 0) #The max length for f in res: if len(f) == lismax: print (str(f)) #An ics of max length

### C++

/* Find a longest increasing subsequence http://basicalgos.blogspot.com/2012/03/37-longest-increasing-sequence-lis.html */ #include <iostream> #include <vector> #include <iterator> #include <algorithm> #include <numeric> typedef std::vector<int> ics_t; typedef ics_t::const_iterator ics_const_iterator_t; typedef ics_t::iterator ics_iterator_t; typedef std::vector<ics_t> ics_set_t; typedef ics_set_t::const_iterator ics_set_const_iterator_t; typedef ics_set_t::iterator ics_set_iterator_t; //-- print functions void print_ics (ics_t const& s) { std::cout << "["; std::ostream_iterator<int> out_it (std::cout, ", "); std::copy (s.begin(), s.end(), out_it); std::cout << "],"; } void print_ics_set (ics_set_t const& ts) { std::cout << "["; ics_set_const_iterator_t begin=ts.begin (), end = ts.end (); ics_set_const_iterator_t t=begin; while (t != end) { print_ics (*t); ++t; } std::cout << "]"; } //-- Calculate the length of an ics std::size_t len_ics (ics_t const& s) { return s.size (); } //-- Calculate the max ics length in a set std::size_t max_ics_len (ics_set_t const& s) { std::vector<std::size_t> lens; std::transform ( s.begin (), s.end (), std::back_inserter (lens), len_ics); return std::accumulate ( lens.begin (), lens.end (), 0, std::max<std::size_t>); } // Extend ts with any new subsequences that can be formed by // prepending s[0] to t for t in ts. struct f // f : ics_set_t * ics_t -> ics_set_t { int s0; f (int s0) : s0 (s0) {} ics_set_t operator()(ics_set_t acc, ics_t const& t) const { if (s0 < t[0]) { ics_t nt (t.size() + 1); nt[0] = s0; for (std::size_t i=0; i < t.size(); ++i) nt[i+1] = t[i]; acc.push_back (nt); return acc; } else { return acc; } } }; //Find the set of increasing subsequences of s. ics_set_t ics (ics_t s) { if (s.size () == 1) { ics_set_t res; res.push_back (s); //s itself is an ics of length 1 return res; } //This is the key point. ics_set_t ts = ics (ics_t(++(s.begin()), s.end())); //ts are the ics values of s - it's first element //Extend ts with any new subsequences that can be formed by //prepending s[0] to t for t in ts. ics_set_t t=std::accumulate (ts.begin (), ts.end(), ts, f(s[0])); t.push_back (ics_t(1, s[0])); return t; } int main () { int data[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1,9, 5, 13, 3, 11, 7, 15 }; ics_t s (data, data + sizeof(data)/sizeof(int)); ics_set_t res = ics (s); std::size_t n=max_ics_len (res); for (std::size_t i = 0; i < res.size (); ++i) { ics_t const& x=res[i]; if (x.size () == n) { print_ics (x); std::cout << std::endl; } } return 0; }