largest independent subsets dynamic programming code example

Example: find weight of lasgerst indepent set array

def max_independant_weight(weights):
    def with_and_without(i):
        if i >= len(weights):
            return 0, 0
        left  = with_and_without(2*i + 1)
        right = with_and_without(2*i + 2)
        return (weights[i] + left[1] + right[1],
                max(left) + max(right))
    return max(with_and_without(0))