longest increasing subsequence

    >>> lis([1, 2, 5, 3, 4])
    [1, 2, 3, 4]
541627
def lis(seq, indices=False):
    '''
    '''
    if not seq:
        return []
    # prevs[i] is the index of the previous element in the longest subsequence
    # containing element i
    prevs = [None] * len(seq)
    # tails[i] is the pair (elem, index) of the lowest element of any
    # subsequence with length i + 1
    tails = [(seq[0], 0)]
    for i, elem in enumerate(seq[1:], start=1):
        if elem > tails[-1][0]:
            prevs[i] = tails[-1][1]
            tails.append((elem, i))
            continue
        # let's find a tail that we can extend
        k = bisect(tails, (elem, -1))
        if tails[k][0] > elem:
            tails[k] = (elem, i)
            if k > 0:
                prevs[i] = tails[k - 1][1]
    _, i = tails[-1]
    subseq = []
    while i is not None:
        subseq.append(i if indices else seq[i])
        i = prevs[i]
    return subseq[::-1]
1248418
def renumber(args):
    
    from jcvi.algorithms.lis import longest_increasing_subsequence
    from jcvi.utils.grouper import Grouper

    p = OptionParser(renumber.__doc__)
    p.set_annot_reformat_opts()

    opts, args = p.parse_args(args)

    if len(args) != 1:
        sys.exit(not p.print_help())

    bedfile, = args

    pf = bedfile.rsplit(".", 1)[0]
    abedfile = pf + ".a.bed"
    bbedfile = pf + ".b.bed"
    if need_update(bedfile, (abedfile, bbedfile)):
        prepare(bedfile)

    mbed = Bed(bbedfile)
    g = Grouper()
    for s in mbed:
        accn = s.accn
        g.join(*accn.split(";"))

    bed = Bed(abedfile)
    for chr, sbed in bed.sub_beds():
        current_chr = chr_number(chr)
        if not current_chr:
            continue

        ranks = []
        gg = set()
        for s in sbed:
            accn = s.accn
            achr, arank = atg_name(accn)
            if achr != current_chr:
                continue
            ranks.append(arank)
            gg.add(accn)

        lranks = longest_increasing_subsequence(ranks)
        print(current_chr, len(sbed), "==>", len(ranks), \
                    "==>", len(lranks), file=sys.stderr)

        granks = set(gene_name(current_chr, x, prefix=opts.prefix, \
                     pad0=opts.pad0, uc=opts.uc) for x in lranks) | \
                 set(gene_name(current_chr, x, prefix=opts.prefix, \
                     pad0=opts.pad0, sep="te", uc=opts.uc) for x in lranks)

        tagstore = {}
        for s in sbed:
            achr, arank = atg_name(s.accn)
            accn = s.accn
            if accn in granks:
                tag = (accn, FRAME)
            elif accn in gg:
                tag = (accn, RETAIN)
            else:
                tag = (".", NEW)

            tagstore[accn] = tag

        # Find cases where genes overlap
        for s in sbed:
            accn = s.accn
            gaccn = g[accn]
            tags = [((tagstore[x][-1] if x in tagstore else NEW), x) for x in gaccn]
            group = [(PRIORITY.index(tag), x) for tag, x in tags]
            best = min(group)[-1]

            if accn != best:
                tag = (best, OVERLAP)
            else:
                tag = tagstore[accn]

            print("\t".join((str(s), "|".join(tag))))
852559
def highlightSubsequence(sequence, x1, x2, start=' [', stop = '] ') :
	"""'"""

	seq = list(sequence)
	print x1, x2-1, len(seq)
	seq[x1] = start + seq[x1]
	seq[x2-1] = seq[x2-1] + stop
	return ''.join(seq)
725817
def chop_sequence(sequence, limit_length):
        
        return [sequence[i:i + limit_length] for i in range(0, len(sequence), limit_length)]
460178
def longest_increasing_subsequence(x):
    
    n = len(x)
    p = [None] * n
    h = [None]
    b = [float('-inf')]  # - infinity
    for i in range(n):
        if x[i] > b[-1]:
            p[i] = h[-1]
            h.append(i)
            b.append(x[i])
        else:
            #   -- binary search: b[k - 1] < x[i] <= b[k]
            k = bisect_left(b, x[i])
            h[k] = i
            b[k] = x[i]
            p[i] = h[k - 1]
    # extract solution
    q = h[-1]
    s = []
    while q is not None:
        s.append(x[q])
        q = p[q]
    return s[::-1]
675125
def _nth(lst, n=1):
    
    n = StringValue(n).value
    lst = ListValue(lst).value
    try:
        n = int(float(n)) - 1
        n = n % len(lst)
    except:
        if n.lower() == 'first':
            n = 0
        elif n.lower() == 'last':
            n = -1
    try:
        ret = lst[n]
    except KeyError:
        lst = [v for k, v in sorted(lst.items()) if isinstance(k, int)]
        try:
            ret = lst[n]
        except:
            ret = ''
    return ret.__class__(ret)
1193943
def longest(*args):
    """"""
    internal_assert(len(args) >= 2, "longest expects at least two args")
    matcher = args[0] + skip_whitespace
    for elem in args[1:]:
        matcher ^= elem + skip_whitespace
    return matcher
679956
def group(self, lst, n):
    
    return itertools.izip(*[itertools.islice(lst, i, None, n) for i in range(n)])
380058
def min_max_indexes(seq):
    
    l = sorted(enumerate(seq), key=lambda s: s[1])
    return l[0][0], l[-1][0]
359931
private static long lcs(String arg0, String arg1, int i, int j) {
        if (arg0.length() == i || arg1.length() == j) {
            return 0;
        }

        if (arg0.charAt(i) == arg1.charAt(j)) {
            return 1 + lcs(arg0, arg1, ++i, ++j);
        } else {
            return Math.max(lcs(arg0, arg1, ++i, j), lcs(arg0, arg1, i, ++j));
        }
    }
605769
def seq_list_nested(b, d, x=0, top_level=True):
    '''
    
    '''
    x += 1

    if d == 0:
        ret = [x]
    else:
        val = x
        ret = []
        for i in range(b):
            lst, x = seq_list_nested(b, d-1, x, False)
            ret.extend(lst)
        ret = [val, ret]
            
    if top_level:
        return ret
    else:
        return ret, x
207670
def consecutivegaps(n, leftmargin = 0, rightmargin = 0):
    """"""
    begin = leftmargin
    while begin < n:
        length = (n - rightmargin) - begin
        while length > 0:
            yield (begin, length)
            length -= 1
        begin += 1
597077
def grouper(n, iterable, fillvalue=None):
    ""
    args = [iter(iterable)] * n
    return zip_longest(fillvalue=fillvalue, *args)
1221436
def subseq(start_offset=0, end_offset=None):
    
    def _(sequence):
        return sequence.subseq(start_offset, end_offset)
    return _
793969
def pairwise_longest(iterable, fillvalue=None):
    ""
    a, b = tee(iterable)
    next(b, None)
    return zip_longest(a, b, fillvalue=fillvalue)
199232
def normalizeSequence(sequence):
  
  seq = np.array(sequence).astype('float64')

  meanSeq = np.mean(seq)
  stdSeq = np.std(seq)
  seq = (seq - np.mean(seq)) / np.std(seq)

  sequence = seq.tolist()
  return sequence, meanSeq, stdSeq
500745
def longest_increasing_subsequence(xs):
    '''
    '''
    # Patience sort xs, stacking (x, prev_ix) pairs on the piles.
    # Prev_ix indexes the element at the top of the previous pile,
    # which has a lower x value than the current x value.
    piles = [[]]  # Create a dummy pile 0
    for x, p in patience_sort(xs):
        if p + 1 == len(piles):
            piles.append([])
        # backlink to the top of the previous pile
        piles[p + 1].append((x, len(piles[p]) - 1))
    # Backtrack to find a longest increasing subsequence
    npiles = len(piles) - 1
    prev = 0
    lis = list()
    for pile in range(npiles, 0, -1):
        x, prev = piles[pile][prev]
        lis.append(x)
    lis.reverse()
    return lis