longest increasing subsequence

0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
*   *         *  *                  *

is there a longer increasing subsequence ?

0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
*        *    *      *    *         *

key observation: if this is index set of LIS ...

         *    *      *    *         *

then this is index set of LIS that ends at + ...

                          +
         *    *      *    *

so suffices to know, for each index j, length LIS that ends there

def longest(S):
  L= [1] # L[j]: length longest subseq. ending at psn j
  for k in range(1,len(S)):
    mymax = 0  # L entries positive, so this init ok
    for j in range(k):
      if S[j]<S[k]: mymax = max(mymax,L[j])
    L.append(1+mymax)
  return L