dp

stuff.py

# max subsequence sum
def max_sub_value(li):
    current_max = 0
    total_max = 0
    for x in li:
        current_max = max(current_max + x, 0)
        total_max = max(current_max, total_max)
    return total_max

print max_sub_value([1, 2, 3, -4, 5])


# making change
def calc_min(denoms, value, min_values):
    if (min_values[value] != 0):
        return min_values[value]

    if (value == 0):
        return ([], 0)

    curr_min = ([], value)
    for coin in denoms:
        if (coin > value):
            break
        res = calc_min(denoms, value - coin, min_values)
        if (1 + res[1] < curr_min[1]):
            curr_min = ([coin] + res[0], 1 + res[1])
    min_values[value] = curr_min
    return min_values[value]


def make_change(denoms, value):
    return calc_min(denoms, value, [0]*(value + 1))

for i in range(1000):
    make_change([2, 3, 5, 6], i)[1]


# maximum increasing subsequence
def increasing_at(li, j):
    if (j == 0):
        return ([li[j]], 1)
    curr_max = ([], 0)
    for i in range(j):
        if li[i] < li[j]:
            res = increasing_at(li, i)
            if (res[1] + 1 > curr_max[1]):
                curr_max = (res[0] + [li[j]], res[1] + 1)
    return curr_max


def longest_inc_subseq(li):
    total_max = ([], 0)
    for i in range(len(li)):
        res = increasing_at(li, i)
        if (res[1] > total_max[1]):
            total_max = res
    return total_max

print longest_inc_subseq([1, 2, 3])