def heaviest_increasing_subsequence(a, debug=False):
    """
    Returns the heaviest increasing subsequence for array a. Elements are (key,
    weight) pairs.

    >>> heaviest_increasing_subsequence([(3, 3), (2, 2), (1, 1), (0, 5)])
    ([(0, 5)], 5)
    """
    # Stores the smallest idx of last element of a subsequence of weight w
    L = {0: -1}
    bestsofar = [(0, -1)] * len(a)  # (best weight, from_idx)
    for i, (key, weight) in enumerate(a):

        for w, j in L.items():
            if j != -1 and a[j][0] >= key:
                continue

            new_weight = w + weight
            if new_weight in L and key <= a[L[new_weight]][0]:
                continue

            L[new_weight] = i
            newbest = (new_weight, j)
            if newbest > bestsofar[i]:
                bestsofar[i] = newbest

        if debug:
            #print (key, weight), L
            print (key, weight), bestsofar

    tb = reversed(list(backtracking(a, L, bestsofar)))
    return [a[x] for x in tb], max(L.items())[0]
dataset/ETHPy150Open tanghaibao/jcvi/algorithms/lis.py/heaviest_increasing_subsequence/swapped operands of `<=`