Return a longest increasing subsequence of xs.

    (Note that there may be more than one such subsequence.)
    >>> longest_increasing_subsequence(range(3))
    [0, 1, 2]
    >>> longest_increasing_subsequence([3, 1, 2, 0])
    [1, 2]
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
403151
function longestIncreasingSubsequence(a) {
	var p = a.slice();
	var result = [];
	result[0] = 0;
	var n = 0;
	var u;
	var v;
	var j;

	for (var i = 0; i < a.length; ++i) {
		var k = a[i];
//		if (k > -1) {
			j = result[n];
			if (a[j] < k) {
				p[i] = j;
				result[++n] = i;
			} else {
				u = 0;
				v = n;

				while (u < v) {
					j = (u + v) >> 1;
					if (a[result[j]] < k) {
						u = j + 1;
					} else {
						v = j;
					}
				}

				if (k < a[result[u]]) {
					if (u > 0) {
						p[i] = result[u - 1];
					}
					result[u] = i;
				}
			}
//		}
	}

	v = result[n];

	while (n >= 0) {
		result[n--] = v;
		v = p[v];
	}

	return result;
}
547068
def split_by_idxs(seq, idxs):
    ''' '''
    last = 0
    for idx in idxs:
        if not (-len(seq) <= idx < len(seq)):
          raise KeyError(f'Idx {idx} is out-of-bounds')
        yield seq[last:idx]
        last = idx
    yield seq[last:]
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]
997976
def next(self):
        
        if self.index < self.length:
            index = self.index
            self.index += 1
            return self.rules[index]
        else:
            raise StopIteration()
324505
def longest_common_substring(s1, s2):
    
    m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in range(1, 1 + len(s1)):
        for y in range(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]
885552
public int[] getNext () {

		if (numLeft.equals (total)) {
			numLeft = numLeft.subtract (BigInteger.ONE);
			return a;
		}

		int temp;

		// Find largest index j with a[j] < a[j+1]

		int j = a.length - 2;
		while (a[j] > a[j+1]) {
			j--;
		}

		// Find index k such that a[k] is smallest integer
		// greater than a[j] to the right of a[j]

		int k = a.length - 1;
		while (a[j] > a[k]) {
			k--;
		}

		// Interchange a[j] and a[k]

		temp = a[k];
		a[k] = a[j];
		a[j] = temp;

		// Put tail end of permutation after jth position in increasing order

		int r = a.length - 1;
		int s = j + 1;

		while (r > s) {
			temp = a[s];
			a[s] = a[r];
			a[r] = temp;
			r--;
			s++;
		}

		numLeft = numLeft.subtract (BigInteger.ONE);
		return a;

	}
793969
def pairwise_longest(iterable, fillvalue=None):
    ""
    a, b = tee(iterable)
    next(b, None)
    return zip_longest(a, b, fillvalue=fillvalue)
970732
function longestPositiveIncreasingSubsequence(ns, newStart) {
  let seq = [],
    is = [],
    l = -1,
    pre = new Array(ns.length);

  for (let i = newStart, len = ns.length; i < len; i++) {
    let n = ns[i];
    if (n < 0) continue;
    let j = findGreatestIndexLEQ(seq, n);
    if (j !== -1) pre[i] = is[j];
    if (j === l) {
      l++;
      seq[l] = n;
      is[l]  = i;
    } else if (n < seq[j + 1]) {
      seq[j + 1] = n;
      is[j + 1] = i;
    }
  }

  for (let i = is[l]; l >= 0; i = pre[i], l--) {
    seq[l] = i;
  }

  return seq;
}
259864
@Override
    public CharSequence subSequence(final int beginIndex, final int endIndex) {
        if (beginIndex < 0) {
            throw new IndexOutOfBoundsException("Negative beginIndex: " + beginIndex);
        }
        if (endIndex > this.len) {
            throw new IndexOutOfBoundsException("endIndex: " + endIndex + " > length: " + this.len);
        }
        if (beginIndex > endIndex) {
            throw new IndexOutOfBoundsException("beginIndex: " + beginIndex + " > endIndex: " + endIndex);
        }
        return CharBuffer.wrap(this.array, beginIndex, endIndex);
    }
354206
def from_ordered_sequence(cls, iseq):
        
        seq = list(iseq)
        # optimize for usually all fits by making longest first
        bst = cls(seq.pop())
        bst._insert_from_ordered_sequence(seq)
        return bst
1239652
def find_near_matches_substitutions(subsequence, sequence, max_substitutions):
    
    _check_arguments(subsequence, sequence, max_substitutions)

    if max_substitutions == 0:
        return [
            Match(start_index, start_index + len(subsequence), 0)
            for start_index in search_exact(subsequence, sequence)
        ]

    elif len(subsequence) // (max_substitutions + 1) >= 3:
        return find_near_matches_substitutions_ngrams(
            subsequence, sequence, max_substitutions,
        )

    else:
        return find_near_matches_substitutions_lp(
            subsequence, sequence, max_substitutions,
        )
729965
def _expand(subsequence, sequence, max_l_dist):
    
    # If given a long sub-sequence and relatively small max distance,
    # use a more complex algorithm better optimized for such cases.
    if len(subsequence) > max(max_l_dist * 2, 10):
        return _expand_long(subsequence, sequence, max_l_dist)
    else:
        return _expand_short(subsequence, sequence, max_l_dist)
9428
def compare_seqs(seqs):
    
    A, B, ignore_gaps = seqs
    a, b = A[1], B[1] # actual sequences
    if len(a) != len(b):
        print('# reads are not the same length', file=sys.stderr)
        exit()
    if ignore_gaps is True:
        pident = calc_pident_ignore_gaps(a, b)
    else:
        pident = calc_pident(a, b)
    return A[0], B[0], pident
115065
def max3(a,b,c)
      (a >= b) ? ((a >= c)? a : c) : ((b >= c)? b : c)
    end
600129
def lcs(s1, s2, i, j):
    
    if i == 0 or j == 0:
        return 0
    elif s1[i - 1] == s2[j - 1]:
        return 1 + lcs(s1, s2, i - 1, j - 1)
    else:
        return max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1))
232625
public function longestCommonSubsequence(array $a, array $b)
    {
        $c = array();

        $m = count($a);
        $n = count($b);

        for ($i = 0; $i <= $m; $i++) {
            $c[$i][0] = 0;
        }

        for ($j = 0; $j <= $n; $j++) {
            $c[0][$j] = 0;
        }

        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($this->matchStrategy->isMatch($a[$i - 1], $b[$j - 1])) {
                    $c[$i][$j] = 1 + (isset($c[$i - 1][$j - 1]) ? $c[$i - 1][$j - 1] : 0);
                } else {
                    $c[$i][$j] = max(
                        isset($c[$i][$j - 1]) ? $c[$i][$j - 1] : 0,
                        isset($c[$i - 1][$j]) ? $c[$i - 1][$j] : 0
                    );
                }
            }
        }

        $lcs = array_pad(array(), $m + 1, 0);
        $this->compileMatches($c, $a, $b, $m, $n, $lcs);

        return $lcs;
    }